我是按照他的想法，算法是自己实现的
给一个字符串，可以把连续相同的部分进行缩写成k（S）的形式，S是一个字符串，k表示有连续相同的S
例如，abgogogogo,可以缩写成ab4（go）。 还可以嵌套缩写，比如
"nowletsgogogoletsgogogo", 缩写成"now2（lets3（go））"
思路：
一道区间dp,但是这题并不好想
f（i, j）表示字符串的i~j位的最小位数
那么
f（i, j） = min{
min{ f（i,k）+f（k+1, j）， i<=k<j },
min{ digitNum（k）+f[l][l+k-1]+2, 如果字符串可以由前k个字符串重复组成的 }
}
digitNum（k）表示数字k的位数
判断区间（i, j）是否有由连续k个组成的字符串连续组成的，直接用O（n）的时间判断
区间DP用记忆画搜索比较容易实现，不用仔细去想迭代的写法
所以以后写区间DP就可以用记忆化搜索的写法
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn = 300;
int dp[maxn][maxn];
char s[maxn];
const int INF = 0x3f3f3f3f;
bool check（int l,int r,int k）
{
int i;
int len = r-l+1;
i=0;
while（i<k）
{
int p;
for（p=1;l+p*k+i<=r;p++）
{
if（s[l+i] != s[l+p*k+i]）
return false;
}
i++;
}
return true;
}
int min（int a,int b）
{
return a<b a:b;
}
int digitnum（int k）
{
int len = 0;
while（k>0）
{
len++;
k/=10;
}
return len;
}
int DP（int l,int r）
{
if（dp[l][r] != -1）
return dp[l][r];
int len = r-l+1;
int d;
dp[l][r] = INF;
for（int k=l;k<r;k++）
dp[l][r] = min（dp[l][r],DP（l,k）+DP（k+1,r））；
for（d=1;d<=len/2;d++）
{
if（len%d != 0）
continue;
if（check（l,r,d））
{
dp[l][r] = min（dp[l][r],digitnum（len/d）+DP（l,l+d-1）+2）；
}
}
return dp[l][r];
}
int main（）
{
int t;
scanf（"%d",&t）；
while（t--）
{
scanf（"%s",s）；
memset（dp,-1,sizeof（dp））；
int len = strlen（s）；
int i;
for（i=0;i<len;i++）
dp[i][i] = 1;
cout《DP（0,len-1）《endl;
}
return 0;
} |