Description
这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵
不能相互重叠。
Input
第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的
分值的绝对值不超过32767)。
Output
只有一行为k个子矩阵分值之和最大为多少。
Sample Input
1 -3
2 3
-2 3
Sample Output
题解
由于$1 leq m leq 2$，我们把m = 1和m = 2分开讨论：
若m = 1，经典$O(nk)$dp。
若m = 2，令$f_{i, j, k}(k in {0,1,2,3,4})$表示前$i$行选$j$个不相交的子矩阵，且第$i$行放置状态为$k$的最大值，其中状态$0,1,2,3,4$分别代表：
0，第$i$行都没有选；1，第$i$行选了左边那个；2，第$i$行选了右边那个；3，第$i$行两个数在同一个子矩阵里；4，第$i$行两个数在两个不同的子矩阵里。
则我们有
$$begin{aligned}
f_{i, j, 0} &= max(f_{i - 1, j, 0}, f_{i - 1, j, 1}, f_{i - 1, j, 2}, f_{i - 1, j, 3}, f_{i - 1, j, 4})\
f_{i, j, 1} &= max(f_{i - 1, j - 1, 0}, f_{i - 1, j, 1}, f_{i - 1, j - 1, 2}, f_{i - 1, j - 1, 3}, f_{i - 1, j, 4})+x\
f_{i, j, 2} &= max(f_{i - 1, j - 1, 0}, f_{i - 1, j - 1, 1}, f_{i - 1, j, 2}, f_{i - 1, j - 1, 3}, f_{i - 1, j, 4})+y\
f_{i, j, 3} &= max(f_{i - 1, j - 1, 0}, f_{i - 1, j - 1, 1}, f_{i - 1, j - 1, 2}, f_{i - 1, j, 3}, f_{i - 1, j - 1, 4})+x+y\
f_{i, j, 4} &= max(f_{i - 1, j - 1, 0}, f_{i - 1, j - 1, 1}, f_{i - 1, j - 1, 2}, f_{i - 1, j - 2, 3}, f_{i - 1, j, 4})+x+y
end{aligned}$$
其中x和y分别是第$i$行的左右两个数。
代码：
#include <algorithm>
#include <cstdio>
using std::max;
int f[105][15][5];
inline int max(int a, int b, int c) {
return max(max(a, b), c);
}
inline int max(int a, int b, int c, int d) {
return max(max(a, b), max(c, d));
}
inline int max(int a, int b, int c, int d, int e) {
return max(e, max(max(a, b), max(c, d)));
}
int main() {
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
if (m == 1) {
int x;
for (int i = 1; i <= n; ++i) {
scanf("%d", &x);
for (int j = 0; j <= k; ++j) {
f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1]);
if (j) f[i][j][1] = max(f[i - 1][j - 1][0], f[i - 1][j][1]) + x;
}
}
printf("%dn", max(f[n][k][0], f[n][k][1]));
} else {
int x, y;
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &x, &y);
for (int j = 0; j <= k; ++j) {
int *now = f[i][j], *las = f[i - 1][j], *las1 = f[i - 1][j - 1], *las2 = f[i - 1][j - 2];
now[0] = max(las[0], las[1], las[2], las[3], las[4]);
if (j) {
now[1] = max(las1[0], las[1], las1[2], las1[3], las[4]) + x;
now[2] = max(las1[0], las1[1], las[2], las1[3], las[4]) + y;
now[3] = max(las1[0], las1[1], las1[2], las[3], las1[4]) + x + y;
if (j > 1)
now[4] = max(las2[0], las1[1], las1[2], las2[3], las[4]) + x + y;
}
}
}
int *ans = f[n][k];
printf("%dn", max(ans[0], ans[1], ans[2], ans[3], ans[4]));
}
return 0;
}
- 还没有人评论，欢迎说说您的想法！
客服
