题目大意：有一串字符串，现在有一种转换规则，如果字符串中出现循环的子串，可以将其转化为 :子串数量(子串)
现在问这个字符串的最短长度

解题思路：区间dp，然后分类讨论，这题的难点是如何再进行缩减
将情况分为两种
一种是区间刚好符合缩减情况的，找出该区间的循环节，看能否继续缩减即可
另一种情况就是普通的区间DP了
以下是一个错误的代码，因为少考虑了其他的缩减情况。
以下代码只考虑了一个能缩减的子串再缩减一个子串的情况，没有考虑到缩减多个子串的情况，比如letsgogogoaaaaaaaletsgogogoaaaaaaaaletsgogogoaaaaaaaa这种情况，以下代码只考虑了缩减letsgogogoaaaaaaaa中的gogogo或者aaaaaaaa而已，没有考虑到同时缩减，所以是错的，但UVA能过，样例强度不够

错误的但能A的代码

#include
   
     #include
    
      #include
     
       using namespace std; #define maxn 210 #define INF 0x3f3f3f3f char str[maxn]; int dp[maxn][maxn]; int vis[maxn][maxn]; int d; int solve(int s, int e) { int len = (e - s + 1) / 2; bool mark = true; int ans, i; for(i = 1; i <= len; i++) if((e - s + 1) % i == 0) { mark = false; for(int j = 0; j < i; j++) { char t = str[s + j]; for(int k = s + j; k <= e; k += i) if(str[k] != t) { mark = true; break; } if(mark) break; } if(!mark) { ans = i; d = i; break; } } if(!mark) { int length; if( (e - s + 1) / ans >= 100) length = 3; else if( (e - s + 1) / ans >= 10) length = 2; else length = 1; if(length + 2 + i <= (e - s + 1)) return length + 2 + i; else return (e - s + 1); } else return (e - s + 1); } int main() { int test; scanf(%d, &test); while(test--) { scanf(%s, str + 1); int len = strlen(str + 1); memset(vis, 0, sizeof(vis)); for(int i = 1; i <= len; i++) dp[i][i] = 1; for(int i = 1; i < len; i++) for(int j = 1; j + i <= len; j++) { int e = j + i; dp[j][e] = solve(j,e); if(dp[j][e] == (e - j + 1)) for(int k = j; k < e; k++) dp[j][e] = min(dp[k + 1][e] + dp[j][k], dp[j][e]); else { vis[j][e] = 1; int t = dp[j][e], Min = dp[j][e]; for(int duan = 3; duan < d; duan++) for(int start = j; start + duan < j + d; start++) { if(vis[start][start + duan]) { Min = min(Min, t - (duan + 1) + dp[start][start + duan]); } } dp[j][e] = Min; } } printf(%d , dp[1][len]); } return 0; } 
     
    
   

改过的代码，如果还有错，还望指出

#include
   
     #include
    
      #include
     
       using namespace std; #define maxn 210 #define INF 0x3f3f3f3f char str[maxn]; int dp[maxn][maxn]; int vis[maxn][maxn]; int d, length; int solve(int s, int e) { int len = (e - s + 1) / 2; bool mark = true; int ans, i; for(i = 1; i <= len; i++) if((e - s + 1) % i == 0) { mark = false; for(int j = 0; j < i; j++) { char t = str[s + j]; for(int k = s + j; k <= e; k += i) if(str[k] != t) { mark = true; break; } if(mark) break; } if(!mark) { ans = i; d = i; break; } } if(!mark) { if( (e - s + 1) / ans >= 100) length = 3; else if( (e - s + 1) / ans >= 10) length = 2; else length = 1; if(length + 2 + i <= (e - s + 1)) return length + 2 + i; else return (e - s + 1); } else return (e - s + 1); } int main() { int test; scanf(%d, &test); while(test--) { scanf(%s, str + 1); int len = strlen(str + 1); memset(vis, 0, sizeof(vis)); for(int i = 1; i <= len; i++) dp[i][i] = 1; for(int i = 1; i < len; i++) for(int j = 1; j + i <= len; j++) { int e = j + i; dp[j][e] = solve(j,e); if(dp[j][e] == (e - j + 1)) for(int k = j; k < e; k++) dp[j][e] = min(dp[k + 1][e] + dp[j][k], dp[j][e]); else { dp[j][e] = min(dp[j][e], length + 2 + dp[j][j + d - 1]); } } printf(%d , dp[1][len]); } return 0; } 
     
    
   

?