BZOJ1068: [SCOI2007]压缩（区间DP）

本文主要是介绍BZOJ1068: [SCOI2007]压缩（区间DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description
　　给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小
写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没
有M，则从串的开始算起）开始的解压结果（称为缓冲串）。 bcdcdcdcd可以压缩为bMcdRR，下面是解压缩的过程
　　另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。
Input
　　输入仅一行，包含待压缩字符串，仅包含小写字母，长度为n。
Output
　　输出仅一行，即压缩后字符串的最短长度。
Sample Input
bcdcdcdcdxcdcdcdcd
Sample Output
12
HINT
在第一个例子中，解为aaaRa，在第二个例子中，解为bMcdRRxMcdRR。

【限制】

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

Source

思路：
定义f(i, j, t),代表区间[i,j]中间有无M,中间没有M才好在中间放R。
默认[i,j]前面有M，因为将区间分开算的时候必须在中间补M。
也即
f[i][j][1] = min(f[i][j][1],min(f[i][k][1],f[i][k][0]) + 1 + min(f[k + 1][j][1],f[k + 1][j][0]));
然后就是判断R能不能放到中间，能的话就舍掉后半段然后加一。
这个过程是个递归过程，此处写了递推。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;char s[105];
int f[105][105][2];//f[i][j][t] t=1代表中间有M
bool same(int x,int y)
{if((y - x + 1) % 2 != 0)return false;int mid = (x + y) >> 1;int l = x;for(int i = mid + 1;i <= y;i++){if(s[l] != s[i])return false;l++;}return true;
}int main()
{scanf("%s",s + 1);int n = (int)strlen(s + 1);for(int l = 1;l <= n;l++){for(int i = 1;i + l - 1 <= n;i++){int j = i + l - 1;int len = j - i + 1;f[i][j][0] = f[i][j][1] = len;for(int k = i;k < j;k++)f[i][j][1] = min(f[i][j][1],min(f[i][k][1],f[i][k][0]) + 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(same(i,j))f[i][j][0] = min(f[i][j][0],f[i][(i + j) >> 1][0] + 1);}}printf("%d\n",min(f[1][n][1],f[1][n][0]));return 0;
}