【HDU 4628】Pieces

相关链接

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4628

解题报告

这题只是划分子序列，于是我们可以状压DP
用枚举子集的话，时间复杂度就是：$O(3^n)$的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

char s[20];
int n,f[1<<17];

inline int read() {
    char c=getchar(); int f=1,ret=0;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}

inline bool judge(int x) {
    int tot=0; char tmp[20];
    for (int i=1;i<=n;i++,x>>=1) {
        if (x&1) {
            tmp[++tot] = s[i];
        }
    }
    for (int i=1,j=tot;i<j;i++,j--) {
        if (tmp[i] != tmp[j]) {
            return 0;
        }
    }
    return 1;
}

int main() {
    for (int T=read();T;T--) {
        memset(f,60,sizeof(f));
        scanf("%s",s+1); 
        n = strlen(s+1);
        for (int i=1,MX=1<<n;i<MX;i++) {
            if (judge(i)) {
                f[i] = 1;
            } else {
                for (int j=i;j;j=(j-1)&i) {
                    f[i] = min(f[i], f[j] + f[i^j]);
                }
            } 
        }    
        printf("%d\n",f[(1<<n)-1]);
    } 
    return 0;
}