正文

UVA - 11584 划分字符串的回文串子串； 简单dp

IP云
IP云V管理员/3 阅读
10/29
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

/**

链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=34398
UVA - 11584 划分字符串的回文串子串； 简单dp
题目大意：
给一个字符串， 要求把它分割成若干个子串，使得每个子串都是回文串。问最少可以分割成多少个。
定义：dp[i]表示前0~i内的字符串划分成的最小回文串个数；
dp[i] = min(dp[j]+1 | j+1~i是回文串）;
先预处理flag[i][j]表示以i~j内的字符串为回文串；
可以通过遍历字符串中心来处理；
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<set>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<cmath>
#include<cctype>
#include<stack>
#include<iomanip>
using namespace std;
typedef pair<int,int> pr;
const int maxn = 1005;
const int inf = 0x3f3f3f3f;
char s[maxn];
bool flag[maxn][maxn];
int dp[maxn], ls;
void dfs(int i,int j)
{
    if(i==0||j>ls) return ;
    if(s[i]==s[j]){
        flag[i][j] = true;
        dfs(i-1,j+1);
    }
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        scanf("%s",s+1);
        ls = strlen(s+1);
  //      cout<<"ls = "<<ls<<endl;
        memset(flag,false,sizeof flag);
 
        for(int i = 1; i <= ls; i++){
            flag[i][i] = true;
            dfs(i,i+1);//令i为偶数回文串中心的左边那个；
            dfs(i-1,i+1); //令i为奇数回文串中心的中间那个；
         //   dfs(i-1,i);  不需要令i为偶数回文串中心的右边那个，因为已经令i为偶数回文串中心的左边那个；中包含了；
        }/*
        for(int i = 1; i <= ls; i++){
            for(int j = 1; j <= ls; j++){
                cout<<"i = "<<i<<"j = "<<j<<"flag[i][j] = "<<flag[i][j]<<endl;
            }
        }*/
        for(int i = 1; i <= ls; i++) dp[i] = inf;
        dp[0] = 0;
        for(int i = 1; i <= ls; i++){
            for(int j = 0; j < i; j++){
                if(flag[j+1][i])
                    dp[i] = min(dp[i],dp[j]+1);
            }
        }
 //       for(int i = 1; i <= ls; i++) cout<<"dp[i] = "<<dp[i]<<endl;
        printf("%d\n",dp[ls]);
    }
    return 0;
}