思路:首先就是状态压缩,然后判断哪些状态是回文串。最后就是动态方程:dp[i]=min(dp[i],dp[j]+1)。这个方程得前提条件是状态(j-i)为回文串。
#include<iostream> #include<cstdio> #include<cstring> #define inf 1<<30 using namespace std; int pl[1<<20],dp[1<<20],n,l; char str[20]; int ispl(int x) { char s[20]; int cnt=0,i; for(i=0;i<=l;i++) { if(x&(1<<i)) s[cnt++]=str[i]; } s[cnt]='