ans[i][j]表示由原串第i个字符到第j个字符组成的子串的最短折叠长度
如果从i到j本身可以折叠，长度就是本身长度或折叠后的长度的最小值
***此处参考：http://blog.csdn.net/a197p/article/details/48701227
（自己只能想到去掉左边或右边字母，这样难以转移状态）
如果不能，就是将其分成两个子串后子串连接起来长度的最小值（如果比本身长度还大则取本身）
如果能折叠的显然一定是折叠比分成两段好，当然如果不确定可以折叠、不折叠都试一下，然后取长度最小值
1 #include<iostream> 2 #include<cstring> 3 #include<string> 4 using namespace std; 5 string str; 6 int ans[110][110]; 7 string ans2[110][110]; 8 void dp(int l,int r) 9 { 10 if(r==l)//由于下面写的是i=1,i<len, 可以在只有1个字符时特判 11 { 12 ans[l][l]=1; 13 ans2[l][l]=str[l]; 14 return; 15 } 16 bool flag,flag2=false; 17 int len=r-l+1,i,j; 18 string temp,temp2; 19 ans2[l][r]=str.substr(l,r-l+1); 20 for(i=1;i<len;i++)//枚举每段i字符，循环暴力求是否是可以折叠的 21 if(len%i==0)//如果每段i字符可以分成整数段 22 { 23 flag=false; 24 temp=str.substr(l,i);//记录下第一段 25 for(j=i;j<len;j+=i) 26 if(temp!=str.substr(l+j,i))//如果分出来的某一段跟第一段不符，就是不能折叠 27 { 28 flag=true; 29 break; 30 } 31 if(flag==false)//如果分出来的所有段都跟第一段相同，就是能折叠 32 { 33 flag2=true; 34 if(ans[l][l+i-1]==0x3f3f3f3f)//曾经忘了，导致无法过UUUUUUUGLUUUUUUUGLZ 35 dp(l,l+i-1);//如果是折叠，只需更新第一段的最小长度 36 //temp2=len/i+48;//这样错的，超过9的数字就不行了 37 char c[20];//存储折叠的次数转换成的字符串 38 sprintf(c,"%d",len/i); 39 temp2=c; 40 temp2+='('+ans2[l][l+i-1]+')'; 41 //temp2的构成是折叠的次数(就是c)+'('+最短的第一段+')' 42 //直接写temp2=c+...会出奇怪的问题，可能跟参与运算的类型太混乱(string,char,char*)有关系 43 if(ans2[l][r].length()>temp2.length())//如果折叠完比原串短或者比之前找到的某种折叠方法短就更新 44 ans2[l][r]=temp2; 45 } 46 } 47 if(flag2==true)//如果能折叠的显然一定折叠比分成左右两段好 48 { 49 ans[l][r]=ans2[l][r].length(); 50 } 51 else 52 { 53 for(i=l;i<r;i++)//分成l~i和(i+1)~r两段，显然i可以为l~(r-1) 54 { 55 if(ans[l][i]==0x3f3f3f3f) 56 dp(l,i); 57 if(ans[i+1][r]==0x3f3f3f3f) 58 dp(i+1,r); 59 if(ans[l][i]+ans[i+1][r]<ans[l][r]) 60 { 61 ans[l][r]=ans[l][i]+ans[i+1][r]; 62 ans2[l][r]=ans2[l][i]+ans2[i+1][r]; 63 } 64 } 65 } 66 } 67 int main() 68 { 69 while(cin>>str) 70 { 71 memset(ans,0x3f,sizeof(ans)); 72 dp(0,str.length()-1); 73 cout<<ans2[0][str.length()-1]<<' '; 74 } 75 return 0; 76 }