题目地址：HDU 4628 这题没想到怎么快速枚举子状态。。。看了题解才知道的。 用for(state=i;state>0;state=(state-1)&i)就可以了。 这题的具体做法是先预处理出所有的状态是不是回文串，，然后就是普通的DP了。 代码如下：
;mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;const int MAXN=100000+10;char s[20], s1[20];int ok[1<<17], dp[1<<17];void init(){memset(dp,INF,sizeof(dp));int len=strlen(s);int tot=1<<len, i, j, cnt, flag;for(i=0;i<tot;i++){cnt=0;for(j=0;j<len;j++){if(i&(1<<j)){s1[cnt++]=s[j];}}flag=0;for(j=0;j<cnt/2;j++){if(s1[j]!=s1[cnt-j-1]){flag=1;break;}}ok[i]=1-flag;}}int main(){int t, len, n, i, state;scanf(“%d”,&t);while(t–){scanf(“%s”,s);init();len=strlen(s);int tot=1<<len;dp[0]=0;for(i=0;i<tot;i++){for(state=i;state>0;state=(state-1)&i){if(ok[state]) dp[i]=min(dp[i],1+dp[state^i]);}}printf(“%d\n”,dp[tot-1]);}return 0;}
也会让你心无旁骛，更会让你的心灵得到解脱和抚慰。
