C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 380K, 提交时间: 2020-07-15 10:41:37

#include <bits/stdc++.h>
using namespace std;
const int maxn=1005;
int dp[110][110][2];
string s;
bool check(int i,int j){
	if((j-i+1)%2!=0) return false;
	int mid=i+j>>1;
	j=mid+1;
	while(i<=mid){
		if(s[i]!=s[j]) return false;
		i++;j++;
	}
	return true;
}
int main(){
	cin>>s;
	int sz=s.size();
	s='#'+s;
	for(int len=1;len<=sz;len++){
		for(int i=1;i+len-1<=sz;i++){
			int j=i+len-1;
			dp[i][j][0]=dp[i][j][1]=len;
			for(int k=i;k<j;k++) 
				dp[i][j][0]=min(dp[i][j][0],dp[i][k][0]+j-k);
			if(check(i,j)) dp[i][j][0]=min(dp[i][j][0],dp[i][(i+j)/2][0]+1);
			for(int k=i;k<j;k++)
				dp[i][j][1]=min(dp[i][j][1],min(dp[i][k][0],dp[i][k][1])+1+min(dp[k+1][j][0],dp[k+1][j][1]));
		}
	}
	cout<<min(dp[1][sz][0],dp[1][sz][1])<<endl;
}

C++(clang++11) 解法, 执行用时: 13ms, 内存消耗: 484K, 提交时间: 2021-02-14 15:07:39

#include<bits/stdc++.h>
using namespace std;
char s[100];
int n;
int dp[55][55][2];
bool check(int l,int r)
{
	if((r-l+1)&1)
	return false;
	for(int i=l;i<=(l+r)/2;i++)
	if(s[i]!=s[i+(r-l+1)/2])
	return false;
	return true;
}
int dfs(int l,int r,bool cur)
{
	if(~dp[l][r][cur])
	return dp[l][r][cur];
	if(l==r)
	return dp[l][r][cur]=1;
	int tans=0x3f3f3f3f;
	if(!cur)
	for(int i=l;i<r;i++)
	tans=min(tans,dfs(l,i,0)+dfs(i+1,r,0)+1);
	for(int i=l;i<r;i++)
	tans=min(tans,dfs(l,i,cur)+r-i);
	if(check(l,r))
	tans=min(tans,dfs(l,(l+r)/2,1)+1);
	return dp[l][r][cur]=tans;
}
int main()
{
	memset(dp,-1,sizeof(dp));
	scanf("%s",s+1);
	n=strlen(s+1);
	printf("%d",dfs(1,n,0));
	return 0;
}

pypy3(pypy3.6.1) 解法, 执行用时: 95ms, 内存消耗: 30504K, 提交时间: 2020-08-02 20:37:11

#!/usr/bin/env python3
#
# [SCOI2007] 压缩
#
import sys, os

s = input().strip()
n = len(s)

def check(i, j):
	if j - i <= 0: return False
	for k in range(j - i):
		if s[i + k] != s[j + k]: return False
	return True

dp = [[None] * (n + 1) for _ in range(n + 1)]

for l in range(1, n + 1):
	for i in range(0, n - l + 1):
		j = i + l
		dp[i][j] = [l, l]
		for k in range(i + 1, j):
			dp[i][j][0] = min(dp[i][j][0], dp[i][k][0] + j - k)
			dp[i][j][1] = min(dp[i][j][1], min(dp[i][k]) + min(dp[k][j]) + 1)
		if l % 2 == 0 and check(i, i + l // 2):
			dp[i][j][0] = min(dp[i][j][0], dp[i][(i + j) >> 1][0] + 1)

print(min(dp[0][-1]))