题目大意：有一串字符串，现在有一种转换规则，如果字符串中出现循环的子串，可以将其转化为 :子串数量(子串) 现在问这个字符串的最短长度
解题思路：区间dp，然后分类讨论，这题的难点是如何再进行缩减 将情况分为两种 一种是区间刚好符合缩减情况的，，找出该区间的循环节，看能否继续缩减即可 另一种情况就是普通的区间DP了 以下是一个错误的代码，因为少考虑了其他的缩减情况。 以下代码只考虑了一个能缩减的子串再缩减一个子串的情况，没有考虑到缩减多个子串的情况，比如letsgogogoaaaaaaaletsgogogoaaaaaaaaletsgogogoaaaaaaaa这种情况，以下代码只考虑了缩减letsgogogoaaaaaaaa中的gogogo或者aaaaaaaa而已，没有考虑到同时缩减，所以是错的，但UVA能过，样例强度不够
错误的但能A的代码
;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;elselength = 1;if(length + 2 + i <= (e – s + 1))return length + 2 + i;elsereturn (e – s + 1);}elsereturn (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\n”, dp[1][len]);}return 0;}
改过的代码，如果还有错，还望指出
;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;elselength = 1;if(length + 2 + i <= (e – s + 1))return length + 2 + i;elsereturn (e – s + 1);}elsereturn (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\n”, dp[1][len]);}return 0;}
去陌生的街角，去做一切我们曾经或现在也很想做的事情，
