Bzoj 1068(区间DP)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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;
}

------ 本文结束 ------