题目:
http://www.lydsy.com/JudgeOnline/problem.php?id=1068
题解:
鸽
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define N 54 using namespace std; int n,f[N][N][2]; char s[N]; inline bool check(int i,int j,int k) { for (int l=0;l<k;l++) if (s[i+l]!=s[j+l]) return 0; return 1; } inline void upt(int &x,const int &y) { if (x>y) x=y; } int main() { scanf("%s",s+1); n=strlen(s+1); memset(f,127/3,sizeof(f)); for (int i=1;i<=n;i++) f[i][i][0]=f[i][i][1]=1; for (int l=1;l<=n;l++) for (int i=1;i<=n;i++) { int j=i+l; if (j>n) break; upt(f[i][j][0],l+1); upt(f[i][j][1],l+1); for (int k=i;k<j;k++) { upt(f[i][j][0],f[i][k][0]+j-k); upt(f[i][j][1],f[i][k][1]+j-k); upt(f[i][j][1],f[i][k][1]+f[k+1][j][1]+1); } if (l&1) { int k=i+j>>1,t=l+1>>1; if (check(i,k+1,t)) upt(f[i][j][1],f[i][k][0]+1),upt(f[i][j][0],f[i][k][0]+1); } } printf("%d ",min(f[1][n][0],f[1][n][1])); return 0; }