Bzoj 1084(区间DP+前缀和)

Bzoj 1084
$m$只有$1, 2$,分情况讨论:
$m=1​$时,就是一个简单的最大连续子段和,设$dp(i,j)​$为前$i​$个数分了$j​$段的最优值
则有$dp(i,j)=max(dp(i-1, j), dp(k,j-1)+S_{i}-S_{k})$,其中$S$是前缀和。
$m=2$时,我们设$dp(i,j,k)​$为第一列前$i$个数第二列前$j$个数分了$k$个矩阵的最优值
则$dp(i,j,k)=max(dp(i-1,j,k), dp(i,j-1,k), dp(l, j, k-1)+S1_i - S1_l, $
$dp(i, l, k-1)+S2_i - S2_l)$,其中$S1$是第一列前缀和,$S2$是第二列前缀和。
当$i=j$时,还可以选择两列一起的大矩阵,则$dp(i,j,k)=max(dp(l,l,k-1)+S1_i+S2_j-S1_l-S2_l)$
初始都要赋值为$-INF$,但是当$j=0$时要赋值为$0$,不然就会导致答案负数。

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100 + 5, MAXK = 10 + 5, INF = 1000000000;
int n, m, k, dp1[MAXN][MAXK], dp2[MAXN][MAXN][MAXK], s1[MAXN], s2[MAXN];
void clean() {
s1[0] = s2[0] = 0;
}
void solve() {
clean();
if (m == 1) {
for (int i=0;i<=n;i++) {
for (int j=1;j<=k;j++) {//1开始,否则没有初值了
dp1[i][j] = -INF;
}
}
for (int i=1;i<=n;i++) {
int x;
scanf("%d", &x);
s1[i] = s1[i - 1] + x;
}
for (int i=1;i<=n;i++) {
for (int j=1;j<=k;j++) {
dp1[i][j] = dp1[i - 1][j];//不选
for (int i1=0;i1<i;i1++) {
dp1[i][j] = max(dp1[i][j], dp1[i1][j - 1] + s1[i] - s1[i1]);
}
}
}
printf("%d\n", dp1[n][k]);
} else {
for (int i=0;i<=n;i++) {
for (int j=0;j<=n;j++) {
for (int l=1;l<=k;l++) {//1开始,否则没有初值了
dp2[i][j][l] = -INF;
}
}
}
for (int i=1;i<=n;i++) {
int x, y;
scanf("%d%d", &x, &y);
s1[i] = s1[i - 1] + x;
s2[i] = s2[i - 1] + y;
}
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
for (int l=1;l<=k;l++) {
dp2[i][j][l] = max(dp2[i - 1][j][l], dp2[i][j - 1][l]);//不选
for (int i1=0;i1<i;i1++) dp2[i][j][l] = max(dp2[i][j][l], dp2[i1][j][l - 1] + s1[i] - s1[i1]);
for (int j1=0;j1<j;j1++) dp2[i][j][l] = max(dp2[i][j][l], dp2[i][j1][l - 1] + s2[j] - s2[j1]);
if (i == j) {//可以选两排一起的一个大矩阵
for (int ij=0;ij<min(i, j);ij++) dp2[i][j][l] = max(dp2[i][j][l], dp2[ij][ij][l - 1] + s1[i] + s2[j] - s1[ij] - s2[ij]);
}
}
}
}
printf("%d\n", dp2[n][n][k]);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
scanf("%d%d%d", &n, &m, &k), solve();
return 0;
}
------ 本文结束 ------