题解 P2470 【[SCOI07]压缩】

Tgotp · 2017-06-24 15:35:28 · 题解

思路：区间dp

具体实现：

f[i][j][k] 代表区间 i - j 间是否存在m；

另默认在i-1处有一个M；

当s[mid+1,r]==s[l,mid]时，f[i][j][0] = f[i][(i+j)/2][0] + 1;

当中间加入了M，枚举M放在哪里就可以；

参照大佬打下的代码。

c++代码如下：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int f[110][110][2];
char s[110];
int n;
bool check(int l,int r)
{
    int mid =(l + r ) /    2;
    for(int i = 1;i <= mid - l + 1 ;i++) if(s[l+i-1] != s[mid+i]) return 0;
    return 1;    
}
int main()
{
    scanf("%s",s+1);
    n = strlen(s+1);
    for(int i = n;i;i--)
        for(int j = i;j<=n;j++)
        {
            f[i][j][0] = f[i][j][1] = j - i + 1;
            for(int k = i;k < j ;k++) f[i][j][1] = min(f[i][j][1],min(f[i][k][0],f[i][k][1]) + 1 + min(f[k+1][j][1],f[k+1][j][0]));
            for(int k = i;k < j ;k++) f[i][j][0] = min(f[i][j][0],f[i][k][0] + j - k);
            if((j - i + 1)%2 == 0 && check(i,j)) f[i][j][0] = f[i][(i+j)/2][0] + 1;
        }
    cout<<min(f[1][n][0],f[1][n][1])<<endl;
    return 0;
}
推广blog：<http://tgotp.science>