本文共 990 字，大约阅读时间需要 3 分钟。

1、

2、题目大意：

letsgogogo可以按照要求简写成lets3(go),简写后的长度是9，而原来的长度是10，问题所求的就是将给定的字符串简写后的最小长度是多少？

要注意可能简写后的长度比原来还要长，那么久要保留原来的长度，因为简写需要考虑3（go）这样的前边重复遍数的这个数字的位数，另一方面还要考虑需要在重复的子串两侧加上（），例如letsgogo,原来长度是8，按照要求简写后是lets2(go),长度是9，所以就要保留原来的长度

因为要求的是0-len-1这一区间的最小长度

设dp[i][j]表示i-j区间的最小长度

那么dp[0][len-1]即所求

dp[i][j]有两种状态，一种是来自于两部分的组合，即dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])

另一种就是来自于组合好的长度

 dp[i][j]=min(dp[i][j],digit(d/p)+dp[i][i+p-1]+2);

其中d是i-j的长度，p是重复子段的长度

3、Ac代码：

#include
   
    #include
    
     #include
     
      using namespace std;#define N 205char s[N];int dp[N][N];int check(int l,int r,int k){    if(l>r)    return 0;    for(int i=l;i<=r;i++)    {        for(int j=0;i+j*k<=r;j++)        {            if(s[i]!=s[i+j*k])            return 0;        }    }    return 1;}int digit(int a){    int sum=0;    while(a)    {        sum++;        a/=10;    }    return sum;}int main(){    int n;    scanf("%d",&n);    while(n--)    {        scanf("%s",s);        int len=strlen(s);        for(int i=0;i
     
    
   

转载地址：http://cgddi.baihongyu.com/