【BZOJ-1068】压缩区间DP

2022-12-25 12:11:35

1068: [SCOI2007]压缩

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 1001 Solved: 615
[Submit][Status][Discuss]

Description

　　给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没有M，则从串的开始算起）开始的解压结果（称为缓冲串）。 bcdcdcdcd可以压缩为bMcdRR，下面是解压缩的过程

　　另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。

Input

　　输入仅一行，包含待压缩字符串，仅包含小写字母，长度为n。

Output

　　输出仅一行，即压缩后字符串的最短长度。

Sample Input

bcdcdcdcdxcdcdcdcd

Sample Output

HINT

在第一个例子中，解为aaaRa，在第二个例子中，解为bMcdRRxMcdRR。

【限制】

100%的数据满足：1<=n<=50 100%的数据满足：1<=n<=50

Source

Solution

区间DP，做的太少了，以至于这道题转移设计出现一点错误，其实这道题写记搜比递推更容易理解.

状态很好想到$f[l][r][0/1]$表示区间$[l,r]$中有M/无M的最短，这样显然答案为$min(f[1][n][0],f[1][n][1])$

转移的时候显然是要枚举断点的，断点为k，转移：

$f[i][j][1]=min(f[i][j][1],min(f[i][k][0],f[i][k][1])+min(f[k+1][j][0],f[k+1][j][1])+1);$

$f[i][j][0]=min(f[i][j][0],f[i][k][0]+j-k);$

然后如果枚举到的区间$[l,r]$，如果这个$[l,r]$可以缩成一个，那么就缩，所以得到$f[i][j][0]=f[i][(i+j)>>1][0]+1$

然后就可以了

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXN 100

char S[MAXN];

int len,f[MAXN][MAXN][];

bool check(int l,int r)

{

    int mid=(l+r)>>;

    if ((r-l+)&) return ;

    for (int i=; i<=mid-l+; i++) if (S[l+i-]!=S[mid+i]) return ;

    return ;

}

int main()

{

    scanf("%s",S+);

    len=strlen(S+);

    for (int i=len; i>=; i--)

        for (int j=i; j<=len; j++)

            {

                f[i][j][]=f[i][j][]=j-i+;

                for (int k=i; k<j; k++)

                    f[i][j][]=min(f[i][j][],min(f[i][k][],f[i][k][])+min(f[k+][j][],f[k+][j][])+);

                for (int k=i; k<j; k++)

                    f[i][j][]=min(f[i][j][],f[i][k][]+j-k);

                if (check(i,j)) f[i][j][]=f[i][(i+j)>>][]+;

                if (j-i+==) f[i][j][]=len+;

            }

    printf("%d\n",min(f[][len][],f[][len][]));

    return ;

}

这道题搞了一会，感觉有点zz

码农公寓