BZOJ1090/SCOI2003/字符串折叠

Posted on By 二价氢

这一题,唔……还是区间DP,和BZOJ1068没有多大区别

表示原字符串从压缩之后的最短串

如果整个串是的重复,那么还有

这里,函数的值如下:

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;
}