DP练习：压缩

· · 题解

传送门：SCOI2007，压缩

  有一个看似正确但实际上错误的做法：

  我们注意到题目中的一句话：R重复从上一个M算起，那么就不能产生嵌套的情况。

  举个栗子：一个位于中间的子串：dzkblrh ak ioi ak ioi dzkblrh ak ioi（空格只是为了方便看清），那么按照上面的策略压缩：

  1.压缩成M dzkblrh ak ioi ak ioi R

  2.压缩成M dzkblrh M ak ioi R R

  然而又因为 R 是和最近的 M 配对的，因此第二个 R 是和第二个 M 配对的，因此展开后是dzkblrh ak ioi ak ioi ak ioi ak ioi，这显然是错误的。

  错误的原因：我们每次压缩的时候都添加了一个 M，使得外层出现的 R 对应到了内层的 M 上，压缩串解压后自然就不是原来的字符串，换言之：内层有无 M 会决定外层能否压缩

  那么我们就以"有无 M "，把 f(i,j) 拆成两种情况。用 1 代表无M，用 2 代表有 M

  还需要搞明白一件事：这个"放 M "的过程，是在当前这个状态里放，还是在上一步（即外层）放。在这里选择第二种方案，原因有二：

  1.因为默认 1 之前是存在 M 的，因此选择第一种方案需要在 i=1 的时候特判

  2. 如果出现了压缩的情况，选择第一种方案是先放个 M ，再把左半边复制出来，再放一个 R，那问题是左半边怎么处理，你要是选择压缩，就回到了一开始的情况；要是不压缩，万一出现左半部分还可以拆分成两个相同的部分（比如说原串是ab ab ab ab），又丢失了最优解。我们发现这样做非常难处理，因此选择第二种。

  因此我们假设推导f(i,j)时， i-1 处已经有了一个 M。这就是我们 "在上一步放 M 的体现"，因为只有一个更大的问题才会用到当前这个问题，而 M 应该是在那个时候放置。这一点在下文会再次提到。

  先来考虑左半边和右半边相等的情况，值得注意的是，只有 f(i,j,0) 才能使用这种情况转移。如果 f(i,j,1) 也用了这个，那么那个"出现的 M "只可能在左半段。还是那个问题，如果这样做，外层的那个 R 就压缩错误了，因此自然不能用。

  然后是枚举断点 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,0),f(k+1,j,1))\end{cases}

  Q：为什么在方程 1 中，左边是f(i,k,0)，右边则是 j-k；而方程 2 中又不是这样呢？

  A；f(i,k)和f(i,j)开头都是相同的，都有一个"自带的"M，因此f(i,k)在不添加多余的 M 情况下，是可以继续压缩的；然而如果想要单独压缩右半部分，必须要在 k 和 k+1 之间插入一个 M，这显然不符合 f(i,j,0) 的定义。而方程2中那个"+1"本身就是代表在 k 和 k+1 之间插入一个 M，此时右半部分不管怎么压缩都不会牵扯到左半部分。

  此时我们再回过头来看。一开始f(1,n)是自带 M 的，压缩成立，后面每次分解的两个子问题，要么是起点还是 1 的，即自带 M ，要么是在开始前先插入了一个 M 再求的，也自然满足压缩的条件。因此这个方案是成立的。

  最后千万不要忘记输出的是 \min(f(1,n,0),f(1,n,1))

  照着本文思路应该很容易打出代码，不过要注意检查左右两遍是否相等的部分比较容易出错。

  代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100;
char str[maxn];
int n,f[maxn][maxn][5];
bool check(int start,int end){
    //check返回[start,end]能否被分割成完全相等的两部分
    int len=(end-start+1)>>1;
    if((end-start+1)%2==1)return false; //特别要注意的是，奇数长度的串要特判（否则你是过不去样例#1的） 
    for(int i=start,j=start+len;i<start+len;i++,j++){
        if(str[i]!=str[j]){
            return false;
        }
    } 
    return true;
}
int main(){
    scanf("%s",str+1); //str+1同样是一个字符数组的地址，这样我这种 for(1..n) 党就非常舒服了
    n=strlen(str+1);
    for(int i=1;i<=n;i++){
        f[i][i][1]=1; //此时就是字符一个本身
        f[i][i][2]=2; //字符本身 加上一个多余的'M' 
    }
    for(int len=2;len<=n;len++){
        for(int i=1;i<=n;i++){
            int j=i+len-1;
            if(j>n)break;
            f[i][j][1]=f[i][j][2]=1e9; //因为是求最小值 
            //如果能分割成左右两部分，用它更新f(i,j,1)
            if(check(i,j)){
                int mid=(i+j)>>1;
                f[i][j][1]=min(f[i][j][1],f[i][mid][1]+1); 
            } 
            //枚举断点k
            for(int k=i;k<j;k++){
                f[i][j][1]=min(f[i][j][1],f[i][k][1]+j-k);
                f[i][j][2]=min(f[i][j][2],min(f[i][k][1],f[i][k][2])+min(f[k+1][j][1],f[k+1][j][2])+1); 
            }
        }
    }
    cout<<min(f[1][n][1],f[1][n][2]);
    return 0;
}