<pre name="code" class="cpp">#include <iostream>#include <stdio.h>#include <string.h>#include <stack>#include <queue>#include <map>#include <set>#include <vector>#include <math.h>#include <bitset>#include <algorithm>#include <climits>using namespace std;#define LS 2*i#define RS 2*i+1#define UP(i,x,y) for(i=x;i<=y;i++)#define DOWN(i,x,y) for(i=x;i>=y;i–)#define MEM(a,x) memset(a,x,sizeof(a))#define W(a) while(a)#define LL long long#define N 505#define MOD 19999997#define INF 0x3f3f3f3f#define EXP 1e-8int dp[N][N],next1[N],cas = 1;char s[N];int kmp(char *s,int len)//kmp求循环节的长度{next1[0] = next1[1] = 0;int i;UP(i,1,len-1){int j = next1[i];W((j&&s[i]!=s[j])){j = next1[j];}if(s[i]==s[j])next1[i+1]=j+1;elsenext1[i+1]=0;}return len-next1[len];}int getbit(int x){int cnt = 0;W(x){x/=10;cnt++;}return cnt;}void DP(){int n = strlen(s+1);int len,l,r,k,i;UP(i,1,n)dp[i][i]=1;UP(len,2,n)//区间dp求解最优值{for(l = 1; l+len-1<=n; l++){r = l+len-1;dp[l][r]=dp[l][l]+dp[l+1][r];UP(k,l+1,r-1){dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);}int t = kmp(s+l,len);if(len%t==0)//现在枚举的串是一个周期循环{int tem = dp[l][l+t-1];if(t>1) tem+=2;//因为不是一个字符的话要加括号tem+=getbit(len/t);//周期数dp[l][r]=min(tem,dp[l][r]);}}}printf("Case %d: %d\n",cas++,dp[1][n]);}int main(){W(~scanf("%s",s+1)){if(s[1]=='0')break;DP();}return 0;}
，总结成功的经验能够让人越来越聪明，
