HDU 4628 Pieces（状态压缩dp）

点击打开链接

题目大意：

给一个字符串，每次可以删除一个可不连续回文子串，问最少删几次可以全部删完。

思路：

因为字符串长度最大16，所以可用二进制状态表示， 1表示选取这个字符，0不选，组成一个子串。

先预处理出所有状态，看这个状态是不是回文。

f[i]表示状态i最少几次可以全删完， 初始化f数组INF

f[i] = min{f[i], f[s]+1 } s是i的子集。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;

typedef long long int64;
const int INF = 0x3f3f3f3f;
const int MAXN = (1<<16)+10;

char str[20];
bool check[MAXN];
int f[MAXN];
int maxSta;

bool isPalind(int st, int len){
    char sub[20];
    int idx = 0;
    for(int i=0; i<len; ++i){
        if( (st>>i)&1 )  
            sub[idx++] = str[i];
    }
    for(int i=0; i<idx/2; ++i){
        if(sub[i] != sub[idx-1-i]) 
            return false;
    }
    return true;
}

int main(){

    int T;
    scanf("%d", &T);
    check[0] = false;
    while(T--){
     
        scanf("%s", str);
        int len = strlen(str);
        maxSta = (1<<len)-1;
        for(int i=1; i<=maxSta; ++i){
            check[i] = isPalind(i, len);                       
        }

        memset(f, 0x7f, sizeof(f));
        f[0] = 0;
        for(int i=1; i<=maxSta; ++i){
            for(int s=i; s; s=(s-1)&i)
                if(check[s])
                    f[i] = min(f[i], f[i^s]+1);
        }
        printf("%d\n", f[maxSta]);

    }
    return 0;
}