题解:[SCOI 2007]压缩

解法:动态规划

思路:设整个字符串长度为n。根据题意,我们可以看作在区间[1,n]之前已经放有一个字母M。那么我们就是要用一些M和R,将字符串中的重复串分割出来,并使最终压缩后的字符串尽量短,本文第一行都说了这是个区间DP了对吧。在例子bcdcdcdcdxcdcdcdcd中,cd我称之为重复串,而其中的cdcdcdcd便是题目所说的缓冲串。

个人认为呢,解题的关键便是重复串和缓冲串的寻找,由此将解题方向指向对M、R位置的寻找。所以我们仅仅需要用动态规划求出M的位置就离成功不远了。如果发现当前处理的字符串中不含M,并且左右两半是一样的,那么就在中点处放一个R并去掉后面那一半就行了。比如:cdcd>>cdRcd>>cdR

然后我们就可以定义数组f[left][right][ok],用f来表示输入中left到right的部分字符串,如果ok=1则表示该部分字符串中有放M,若ok=0则反之。

现在来考虑考虑边界情况:

首先来#define INF 0x3f3f3f3f 弄个大数字吧(别问我为什么hhhhh)

边界条件是f[][][0]=1(只有一个字符不能放M呢,不然就更大了。你看b还要压缩吗),f[][][1]=INF

这边界条件怎么出来的应该一个个自己想一会都想得出吧……

我懒就懒得解释了……再说了你们那么聪明肯定会懂的对吧!

最后print出一个最小值就OK了。

程序自己看咯,建议对照着上面的文字看,更容易看得懂。

Code:

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm> 
#define maxn 55
#define INF 0x3f3f3f3f
using namespace std;
int f[maxn][maxn][2],n;
char st[maxn];
bool bo(int left,int right) {
    if ((right-left+1)&1)return false;
    int m=(left+right)>>1;
    for (int i=left; i<=m; i++)if(st[i]!=st[m+i-left+1])return false;
    return true;
}
int dp(int left,int right,bool ok) {
    if (f[left][right][ok]<INF)return f[left][right][ok];
    int len=right-left+1;
    if (len==1) return ok?f[left][right][ok]=INF:f[left][right][ok]=1;
    int m=(left+right)>>1;
    if (ok) {
        for (int i=left; i<right; i++) {
            f[left][right][ok]=min(f[left][right][ok],dp(left,i,1)+1+dp(i+1,right,1));
            f[left][right][ok]=min(f[left][right][ok],dp(left,i,0)+1+dp(i+1,right,1));
            f[left][right][ok]=min(f[left][right][ok],dp(left,i,1)+1+dp(i+1,right,0));
            f[left][right][ok]=min(f[left][right][ok],dp(left,i,0)+1+dp(i+1,right,0));
        }
        return f[left][right][ok];
    }
    if (bo(left,right))f[left][right][ok]=dp(left,m,0)+1;
    for (int i=left; i<right; i++)
        f[left][right][ok]=min(f[left][right][ok],dp(left,i,0)+right-i);
    return f[left][right][ok];
}
int main() {
    memset(f,INF,sizeof(f));
    scanf("%s",st+1); n=strlen(st+1);
    printf("%d\n",min(dp(1,n,0),dp(1,n,1)));
    return 0;
}

点我回到主页

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google photo

You are commenting using your Google account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s