uva 11584 Partitioning by Palindromes

紫皮书！

题意：给你小写字母组成的字符串，让你划分为尽量少的回文串。

思路：dp[i] 为0 - i 划分的最小的回文串的个数 则 dp[i] = min{dp[i],dp[j]+1} 如果 j+1 到 i 是回文串的话 （PS： 是 j+1 到 i 是回文串 而不是 j 到 i 是回文串）

先把 从 i - j 是回文串 处理一下然后dp

总之水题……

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
const int INF = 0xfffffff;
const double ESP = 10e-8;
const double Pi = atan(1) * 4;
const int MOD = 1000007;
const int MAXN = 1000 + 10;
typedef long long LL;
using namespace std;

char str[MAXN];
bool isPart[MAXN][MAXN];
int dp[MAXN];
int main(){
    //freopen("input.txt","r",stdin);
    int n;
    scanf("%d",&n);
    while(n--){
        scanf("%s",str);
        memset(isPart,0,sizeof(isPart));
        int len = strlen(str);
        for(int i = 0;i < len;i++){
            for(int j = i;j < len;j++){
                bool flag = 1;
                for(int k = 0;k <= (j-i)/2;k++){
                    if(str[k+i] != str[j-k]){
                        flag = 0;
                        break;
                    }
                }
                if(flag){
                    isPart[i+1][j+1] = isPart[j+1][i+1] = 1;
                }
            }
        }
        for(int i = 1;i <= len;i++){
            dp[i] = INF;
        }
        dp[1] = 1;
        for(int i = 1;i <= len;i++){
            for(int j = 0;j < i;j++){
                if(isPart[j+1][i]){
                    dp[i] = min(dp[i],dp[j]+1);
                }
            }
        }
        printf("%d
",dp[len]);
    }
    return 0;
}