【传送门：BZOJ1090】
简要题意：
给出一个字符串，可以将相邻的重复的子串合并在一起，如：abaaaabba，可以合并为ab4(a)bba
注意，数字和括号均算作字符，数字有多少位就相当于有多少个字符
请问怎么合并才能使字符串的长度最小（也可以不合并）
题解：
区间DP，本来想着会T，结果应该是不会询问这么多遍，所以耗时可观
f[i][j]表示第i个字符到第j个字符所组成的子串合并后的最短长度
一般情况下f[i][j]=min(f[i][j],f[i][k]+f[k+1][j])
如果可以合并呢？
那我们就枚举将要合并的子串长度，然后找开头结尾，然后判断是否为循环串，如果是的话，就加多一步操作：
f[i][j]=min(f[i][j],f[i][k]+2+calc(i,k,j))calc表示这个循环节循环的次数的位数
最后输出f[1][n]就行了，n表示整个串的长度
参考代码：
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; char st[110]; int f[110][110]; bool check(int l,int mid,int r) { if((r-mid)%(mid-l+1)!=0) return false; int len=mid-l+1; for(int i=mid+1;i<=r;i++) { int t=(i-mid)%mid; if(t==0) t=mid; if(st[i]!=st[t+l-1]) return false; } return true; } int calc(int l,int mid,int r) { int t=(r-mid)/(mid-l+1)+1; int tt=0; while(t!=0){t/=10;tt++;} return tt; } int main() { scanf("%s",st+1); int n=strlen(st+1); memset(f,63,sizeof(f)); for(int i=1;i<=n;i++) f[i][i]=1; for(int s=2;s<=n;s++) { for(int i=1;i+s-1<=n;i++) { int j=i+s-1; for(int k=i;k<j;k++) { f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]); if(check(i,k,j)==true) f[i][j]=min(f[i][j],f[i][k]+2+calc(i,k,j)); } } } printf("%d ",f[1][n]); return 0; }