这一题，唔……还是区间DP，和BZOJ1068没有多大区别
用\(f_{i,j}\)表示原字符串从\(i\)到\(j\)压缩之后的最短串
则
\[f_{i,j}=\min\{f_{i,k}+f_{k,j}\}(i\le k < j)\]如果整个串是\(i\)到\(k\)的重复，那么还有
\[f_{i,j}=\min\{f_{i,k}+2+T(k-i+1)\}\]这里，函数\(T(x)\)的值如下：
| \(x\) | \(T(x)\) |
|---|---|
2~9 |
1 |
10~99 |
2 |
100+ |
3 |
再加上记忆化搜索就能够AC了
AC-Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=105;
char Data[MAXN];
int f[MAXN][MAXN];
bool vis[MAXN][MAXN];
int GetT(int a)
{
if (a<10)
return 1;
else if (a<100)
return 2;
else return 3;
}
bool Check(int a,int b,int c,int d)
{
int x=b-a+1,y=d-c+1;
if (x%y)
return false;
for (int i=1;i<=x/y;i++)
{
for (int j=(i-1)*y+1,k=c;j<=i*y;j++,k++)
{
if (Data[j+a-1]!=Data[k])
return false;
}
}
return true;
}
int dp(int l,int r)
{
if (vis[l][r])
return f[l][r];
vis[l][r]=true;
int len=r-l+1;
f[l][r]=len;
if (l==r)
return f[l][r]=1;
for (int i=l;i<r;i++)
{
f[l][r]=min(f[l][r],dp(l,i)+dp(i+1,r));
if (Check(l,i,i+1,r))
f[l][r]=min(f[l][r],dp(i+1,r)+2+GetT(len/(r-i)));
}
return f[l][r];
}
int main()
{
scanf("%s",Data+1);
printf("%d\n",dp(1,strlen(Data+1)));
return 0;
}