CSU 1620: A Cure for the Common Code（KMP+区间DP）

#include<stdio.h>
#include<string.h>
const int N = 505;int next1[N];
char s[N];void getNext(int l,int len){int i=0, j=-1;next1[0]=-1;while(i<len){if(j==-1||s[l+i]==s[l+j]){i++; j++;next1[i]=j;}elsej=next1[j];}
}int main(){int c=0,dp[N][N];while(scanf("%s",s)>0&&s[0]!='0'){int len=strlen(s);for(int i=0;i<len;i++)dp[i][i]=1;for(int k=1;k<len;k++)for(int i=0;i+k<len;i++){int j=i+k;dp[i][j]=1+dp[i+1][j];for(int e=i;e<j;e++)if(dp[i][j]>dp[i][e]+dp[e+1][j])dp[i][j]=dp[i][e]+dp[e+1][j];//------整个子串计算一次-------getNext(i,k+1);int t=k+1-next1[k+1];//得循环节长度if((k+1)%t==0){int ans=dp[i][i+t-1];//循环部分的字符串最优解if(t>1)ans+=2;  //循环部分的字符串长度>1，则加一对括号t=(k+1)/t;      //有多少个循环部分while(t)ans++,t/=10; //位数if(dp[i][j]>ans)dp[i][j]=ans;}}printf("Case %d: %d\n",++c,dp[0][len-1]);}
}