C++(g++ 7.5.0) 解法, 执行用时: 4ms, 内存消耗: 492K, 提交时间: 2022-07-31 15:00:26

#include <bits/stdc++.h>
using namespace std;
int s1[104], f[104][104];
char s[105];
int check(int l, int r, int len){
	for(int i = l; i <= r; i++){
		if(i + len <= r && s[i] != s[i + len]) return 0;
	}
	return 1;
}
int main(){
	int i, j, n, m, k, t, l;
	for(i = 2; i <= 9; i++) s1[i] = 1;
	for(i = 10; i <= 99; i++) s1[i] = 2;
	s1[100] = 3;
	scanf("%s", s);
	n = strlen(s);
	memset(f, 1, sizeof(f));
	for(i = 0; i < n; i++) f[i][i] = 1;
	for(i = n - 1; i >= 0; i--){
		for(j = i + 1; j < n; j++){
			l = j - i + 1;
			for(k = i; k < j; k++) f[i][j] = min(f[i][j], f[i][k] + f[k+1][j]);
			for(k = i; k < j; k++){
				t = k - i + 1;
				if(l % t != 0) continue;
				if(check(i, j, t)) f[i][j] = min(f[i][j], s1[l / t] + 2 + f[i][k]);
			}
		}
	}
	printf("%d", f[0][n-1]);
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 896K, 提交时间: 2019-08-20 16:16:47

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[10005][10005],n;char a[110000];
bool check(int i,int k,int j)
{
	if((j-k)%(k-i+1)) return false;
	int p=i;
	for(int t=k+1;t<=j;++t)
	{
		if(a[t]!=a[p]) return false;
		if(++p>k) p=i;
	}
	return true;
}
int calc(int x)
{
	int b=0;
	for(;x;x/=10) ++b;
	return b;
}
int main()
{
	scanf("%s",a+1);
	n=strlen(a+1);
	for(int i=1;i<=n;++i)
	for(int j=i;j<=n;++j)
	dp[i][j]=j-i+1;
	for(int i=n;i>=1;--i)
    for(int j=i+1;j<=n;++j)
    for(int k=i;k<j;++k)
    {
    	dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
    	if(check(i,k,j)) dp[i][j]=min(dp[i][j],dp[i][k]+2+calc((j-k)/(k-i+1)+1));
	}
	cout<<dp[1][n]<<endl;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 820K, 提交时间: 2021-08-16 14:35:34

#include<bits/stdc++.h>
using namespace std;
int dp[10005][10005],o;
char a[1000000];
bool check(int i,int k,int j) {
	if((j-k)%(k-i+1)) return false;
	int p=i;
	for(int t=k+1; t<=j; ++t) {
		if(a[t]!=a[p]) return false;
		if(++p>k) p=i;
	}
	return true;
}
int calc(int x) {
	int b=0;
	for(;x; x/=10) ++b;
	return b;
}
int main() {
	scanf("%s",a+1);
	o=strlen(a+1);
	for(int i=1; i<=o; ++i)
		for(int j=i; j<=o; ++j)
			dp[i][j]=j-i+1;
	for(int i=o; i>=1; --i)
		for(int j=i+1; j<=o; ++j)
			for(int k=i; k<j; ++k) {
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
				if(check(i,k,j)) dp[i][j]=min(dp[i][j],dp[i][k]+2+calc((j-k)/(k-i+1)+1));
			}
	cout<<dp[1][o]<<endl;
}