hdu 4628 Pieces

题意：给你一个串，每次只能删除一个回文串，求删完所有的串最少需要多少步

思路：枚举所有状态，然后判断他们是不是回文串，对其进行标记，然后就是一个动规的问题，对于每个串然后进行转移，最后转移成母串，输出答案

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int vis[1<<16];
int dp[1<<16];
char s[16],ss[16];
int cnt;

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%s",s);
        memset(vis,0,sizeof(vis));
        int n=strlen(s);        
        for(int i=0;i<(1<<n);i++){
            cnt=0;
            for(int j=0;j<n;j++){
                if((i>>j)&1)ss[cnt++]=s[j];
            }
            vis[i]=1;
            for(int j=0,k=cnt-1;j<k;j++,k--){
                if(ss[j]!=ss[k]){
                    vis[i]=0;break;
                }
            }
        }
        dp[0]=0;
        for(int i=1;i<(1<<n);i++){
            dp[i]=0x3f;
            for(int j=i;j>0;(--j)&=i){
                if(vis[j])dp[i]=min(dp[i],dp[i-j]+1);
            }
        }
        printf("%d
",dp[(1<<n)-1]);
    }
    return 0;
}