我是按照他的想法，算法是自己實現的 給一個字符串，可以把連續相同的部分進行縮寫成k(S)的形式，S是一個字符串，k表示有連續相同的S 例如，abgogogogo，可以縮寫成ab4(go). 還可以嵌套縮寫，比如 “nowletsgogogoletsgogogo”， 縮寫成“now2(lets3(go))” 思路： 一道區間dp，但是這題並不好想 f(i, j)表示字符串的i~j位的最小位數 那麼 f(i, j) = min{ min{ f(i,k)+f(k+1, j), i<=k<j }， min{ digitNum(k)+f[l][l+k-1]+2, 如果字符串可以由前k個字符串重復組成的 } } digitNum(k)表示數字k的位數 判斷區間（i, j）是否有由連續ｋ個組成的字符串連續組成的，直接用Ｏ(n)的時間判斷 區間DP用記憶畫搜索比較容易實現，不用仔細去想迭代的寫法 所以以後寫區間DP就可以用記憶化搜索的寫法 代碼： #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<string.h> using namespace std; const int maxn = 300; int dp[maxn][maxn]; char s[maxn]; const int INF = 0x3f3f3f3f; bool check(int l,int r,int k) { int i; int len = r-l+1; i=0; while(i<k) { int p; for(p=1;l+p*k+i<=r;p++) { if(s[l+i] != s[l+p*k+i]) return false; } i++; } return true; } int min(int a,int b) { return a<b?a:b; } int digitnum(int k) { int len = 0; while(k>0) { len++; k/=10; } return len; } int DP(int l,int r) { if(dp[l][r] != -1) return dp[l][r]; int len = r-l+1; int d; dp[l][r] = INF; for(int k=l;k<r;k++) dp[l][r] = min(dp[l][r],DP(l,k)+DP(k+1,r)); for(d=1;d<=len/2;d++) { if(len%d != 0) continue; if(check(l,r,d)) { dp[l][r] = min(dp[l][r],digitnum(len/d)+DP(l,l+d-1)+2); } } return dp[l][r]; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%s",s); memset(dp,-1,sizeof(dp)); int len = strlen(s); int i; for(i=0;i<len;i++) dp[i][i] = 1; cout<<DP(0,len-1)<<endl; } return 0; }
