C++ 解法, 执行用时: 898ms, 内存消耗: 1640K, 提交时间: 2021-12-24 14:10:34

#include<bits/stdc++.h>
using namespace std;
const int maxn=500;
int dp[maxn][maxn];
bool vis[maxn][maxn];
char s[maxn];
bool check(int l,int r,int cl,int cr)
{
    if((r-l+1)%(cr-cl+1)!=0)return false;
    for(int i=l;i<=r;i++)
    {
        if(s[i]!=s[(i-l)%(cr-cl+1)+cl])return false;
    }
    return true;
}
int calc(int x)//x是几位数
{
    int ans=0;
    while(x)
    {
        x/=10;
        ans++;
     }
     return ans;
}
 
int dfs(int l,int r)
{
    if(l==r)return 1;
    if(vis[l][r])return dp[l][r];
    vis[l][r]=true;
    dp[l][r]=r-l+1;
    for(int i=l;i<r;i++)
    {
        dp[l][r]=min(dp[l][r],dfs(l,i)+dfs(i+1,r));
        if(check(i+1,r,l,i))
        {
            if(i-l>0) dp[l][r]=min(dp[l][r],dfs(l,i)+2+calc((r-i)/(i-l+1)+1));
            else dp[l][r]=min(dp[l][r],dfs(l,i)+calc((r-i)/(i-l+1)+1));
        }
    }
    return dp[l][r];
}
int main() {
    int jjj = 1;
    char stop='0';
    while (scanf("%s", s) != EOF) {
        if (s[0] == stop){
            break;
        }

        int sum = dfs(0, strlen(s) - 1);
        cout << "Case " << jjj << ": " << sum << "\n";
        jjj += 1;
        memset(dp, '\0', sizeof(dp));
        memset(vis,0, sizeof(vis));
    }
}

C 解法, 执行用时: 200ms, 内存消耗: 1176K, 提交时间: 2021-12-20 19:19:14

#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;
        }
        else
            j=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]);
    }
}

Python3 解法, 执行用时: 2769ms, 内存消耗: 10380K, 提交时间: 2021-12-24 09:50:37

import functools
import sys
 
sys.setrecursionlimit(2000)
@functools.lru_cache(None)
def encode(s):
    res = s
    for i in range(1,len(s)+1):
        tmp = s[:i]
        res = min(res, tmp +encode(s[i:]), key=len)
        cnt = 1
        j = i
        while s[j:].find(tmp) == 0:
            cnt += 1
            j += len(tmp)
            if len(tmp)>1:
                res = min(res, str(cnt) + "(" + encode(tmp) + ")" + encode(s[j:]), key=len)
            else:
                res = min(res, str(cnt) + encode(tmp) + encode(s[j:]), key=len)
    return res
 
def main():
    hasInput=True
    count_line = 0
    while hasInput:
        count_line += 1
        string = sys.stdin.readline().strip()
        if string == '0':
            hasInput = False
            break
        numstr = encode(string)
        num = len(numstr)
        print(("Case "+str(count_line)+": "+str(num)))
main()