「Bzoj 1068」「SCOI2007」压缩 (区间DP)

Bzoj 1068
区间划分DP，按照压缩前后，只压缩前，只压缩后，压缩整个的思路来做，具体看下面图片，代码中也有注释。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 50 + 5;
char s[MAXN];
int n, f[MAXN][MAXN][2];
//f(i,j,0/1)表示[i,j]中不含有/可能含有"M", 且i和i-1之间有一个"M"("M"的长度不计入当前状态)时的压缩长度 
bool isTheSame(int a, int b) {//是否满足 [a, M] = [M+1, b]
    int len = b - a + 1;
    if (len & 1) return false;
    for (int i=1;i<=len/2;i++) {
        if (s[i + a - 1] != s[i + a - 1 + len / 2]) return false;
    }
    return true;
}
int dp(int i, int j, int t) {
    int len = j - i + 1, tmp = len;
    if (f[i][j][t] >= 0) return f[i][j][t];
    if (len == 1) return f[i][j][t] = 1;
    //前一段 后一段 都压缩 
    if (t) for (int k=i;k<j;k++) tmp = min(tmp, dp(i, k, 1) + 1 + dp(k + 1, j, 1));
    //只压缩前一段
    for (int k=i;k<j;k++) tmp = min(tmp, dp(i, k, t) + j - k);
    if (t) for (int k=i;k<j;k++) tmp = min(tmp, dp(i, k, 0) + j - k);//可写可不行，dp(i,k,0)包含在了dp(i,k,1)中
     //只压缩后一段
    if (t) for (int k=i;k>j;k++) tmp = min(tmp, dp(i, j, 1) + 1 + k - i + 1);//可写可不行，这种情况包含在了 都压缩 的情况中 
    //特殊
    if (isTheSame(i, j)) tmp = min(tmp, dp(i, i + len / 2 - 1, 0) + 1);//串是由相同的两段组成的，直接放R 
    return f[i][j][t] = tmp;
}
void clean() {
    ms(f, -1);
}
void solve() {
    clean();
    n = strlen(s + 1);
    printf("%d\n", dp(1, n, 1));
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    scanf("%s", s + 1), solve();
    return 0;
}