BZOJ1068/SCOI2007/压缩

Posted on By 二价氢

这一题,唔……区间DP

表示这一串字符中,能否()加入R的最短字符串

如果,我们能够在这一段文字中加R,那么就是这样

对于所有的串,都能够这样:

如果串的长度为偶数,那么就能这样

枚举然后答案就是这三者中的最小值

再加上记忆化搜索就能够AC了

AC-Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=55;
bool vis[MAXN][MAXN][2];
int f[MAXN][MAXN][2];
char data[MAXN];
bool compare(int s1,int s2)
{
    int len=s2-s1;
    for (int i=0;i<len;i++)
        if (data[s1+i]!=data[s2+i])
            return false;
    return true;
}
int dp(int l,int r,bool add)
{
    int len=r-l+1;
    int ret=len;
    if (l==r)
        return 1;
    if (vis[l][r][add])
        return f[l][r][add];
    vis[l][r][add]=true;
    for (int i=l;i<r;i++)
    {
        if (add)
            ret=min(ret,dp(l,i,1)+dp(i+1,r,1)+1);
        ret=min(ret,dp(l,i,add)+r-i);//dp(l,i,add)+1+r-i-1
    }
    if (len%2==0)
        if (compare(l,l+len/2))
            ret=min(ret,dp(l,l+len/2-1,0)+1);
    return f[l][r][add]=ret;
}
int main()
{
    scanf("%s",data+1);
    printf("%d\n",dp(1,strlen(data+1),1));
    return 0;
}