Bzoj 1090(区间DP)

Bzoj 1090
这题和Bzoj 1068差不多,但是简单一些,1068的一个M对应很多R,而1090括号一一对应,使得这题的转移变得非常简单了。
设$f(i,j)$为$[i,j]$折叠后的长度(包括括号的长度)
考虑枚举中间点,$f(i,j)=min(f(i,k)+f(k+1,j))$
而只压缩前后的情况,由于括号一一对应,所以这些情况都在上面的情况之中了,不同于1068
而整个区间压缩,$f(i,j)=min(f(i,i+k-1)+cal(len/k)$,其中$len=j-i+1$.当且仅当$[i,j]$为长为$k$的子串循环而来,$cal(k)$用来计算括号的长度
边界值:$f(i,i)=1$,所有$f(i,j)$初始化为$j-i+1$
然后就可以DP了,同样记忆化搜索好写一些,用记忆化,不用考虑枚举顺序

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 = 100 + 5;
char s[MAXN];
int n, f[MAXN][MAXN];
int cal(int x) {//返回括号占位
if (x == 1) return 0;
if (x < 10) return 1 + 2;
if (x < 100) return 2 + 2;
return 3 + 2;
}
bool check(int i, int j, int k) {//是否是长为k的子串循环而来
int len = j - i + 1;
if (len % k != 0 || i + k - 1 > n) return false;
for (int a = 1; a < len / k; a++) {
for (int b = 1; b <= k; b++) {
if (s[i + b - 1] != s[i + b + a * k - 1]) return false;
}
}
return true;
}
int dp(int i, int j) {
int len = j - i + 1, tmp = len;
if (f[i][j] >= 0) return f[i][j];
if (len == 1) return f[i][j] = 1;
for (int k = i; k < j; k++) tmp = min(tmp, dp(i, k) + dp(k + 1, j));
for (int k = 1; k <= len / 2; k++) if (check(i, j, k)) tmp = min(tmp, dp(i, i + k - 1) + cal(len / k));
return f[i][j] = tmp;
}
void clean() {
ms(f, -1);
}
void solve() {
clean();
n = strlen(s + 1);
printf("%d\n", dp(1, n));
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
scanf("%s", s + 1), solve();
return 0;
}

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