题目链接：BZOJ - 1084
题目分析
我看的是神犇BLADEVIL的题解。
1）对于 m = 1 的情况， 首先可能不取 Map[i][1]，先 f[i][k] = f[i - 1][k]; 再考虑取一段新的的情况，用 max(f[j][k - 1] + Sum[i][1] - Sum[j][1]) (0 <= j < i) 更新 f[i][j]；
2) 对于 m = 2 的情况，用 f[i][j][k] 表示左列取到第 i 个，右列取到第 j 个，共 k 个矩形的最优值。
首先还是可能不取新的矩形，那么 f[i][j][k] = max(f[i - 1][j][k], f[i][j - 1][k]);
之后可能左列取一个新的矩形，用 max(f[ii][j][k - 1] + Sum[i][1] - Sum[ii][1]) (0 <= ii < i) 更新 f[i][j][k];
可能在右列取一个新的矩形，用 max(f[i][jj][k - 1] + Sum[j][2] - Sum[jj][2]) (0 <= jj < j) 更新 f[i][j][k];
若 i == j, 那么可能取一个跨两列的矩形，用 max(f[ii][ii][k - 1] + Sum[i][1] + Sum[i][2] - Sum[ii][1] - Sum[ii][2]) (0 <= ii < i) 更新 f[i][j][k];
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath> using namespace std; const int MaxN = 100 + 5, MaxK = 10 + 5; int n, m, EK;
int Map[MaxN][3], Sum[MaxN][3], f1[MaxN][MaxK], f2[MaxN][MaxN][MaxK]; inline int gmax(int a, int b) {return a > b ? a : b;}
inline int gmin(int a, int b) {return a < b ? a : b;} int main()
{
scanf("%d%d%d", &n, &m, &EK);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%d", &Map[i][j]);
Sum[i][j] = Sum[i - 1][j] + Map[i][j];
}
}
if (m == 1) {
for (int i = 1; i <= n; ++i) {
for (int k = 1; k <= EK; ++k) {
f1[i][k] = f1[i - 1][k];
for (int j = 0; j < i; ++j) {
f1[i][k] = gmax(f1[i][k], f1[j][k - 1] + Sum[i][1] - Sum[j][1]);
}
}
}
printf("%d\n", f1[n][EK]);
}
else {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= EK; ++k) {
f2[i][j][k] = gmax(f2[i - 1][j][k], f2[i][j - 1][k]);
for (int jj = 0; jj < i; ++jj)
f2[i][j][k] = gmax(f2[i][j][k], f2[jj][j][k - 1] + Sum[i][1] - Sum[jj][1]);
for (int jj = 0; jj < j; ++jj)
f2[i][j][k] = gmax(f2[i][j][k], f2[i][jj][k - 1] + Sum[j][2] - Sum[jj][2]);
if (i == j) {
for (int jj = 0; jj < i; ++jj)
f2[i][j][k] = gmax(f2[i][j][k], f2[jj][jj][k - 1] + Sum[i][1] + Sum[i][2] - Sum[jj][1] - Sum[jj][2]);
}
}
}
}
printf("%d\n", f2[n][n][EK]);
}
return 0;
}