自动搬运

查看原文

来自洛谷，原作者为

	Drifty zzzzzzᙆᙆᙆᙆᙆᙆ

搬运于2025-08-24 23:03:03，当前版本为作者最后更新于2024-10-15 21:32:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Solution

介绍一下蓝书上的 dp 做法。

注意到本题的阶段满足线性增长的特性，考虑线性 dp。

我们设状态 $f_{i,j,l,r,x,y}$ 表示前 $i$ 行选了 $j$ 个格子，当前的第 $i$ 行选了 $l\sim r$ 个格子（包括第 $l,r$ 个格子，若不选 $l, r$ 均为零），左边界是否在扩张（即列号的单调性）记为 $x$，右边界是否在扩张记为 $y$。其中：

• $x = 1$ 左边界扩张，$x = 0$ 左边界收缩。
• $y = 0$ 右边界扩张，$y = 1$ 右边界收缩。

以下记：

$$S_{l, r} = \sum_{p = l} ^ {r} a_{i,p}$$

对 $x,y$ 进行分讨，有以下转移。

$$f_{i, j, l, r, 1, 1} = S_{l, r} + \max_{l\le p \le r\le q} \left \{ \max_{0\le y\le 1} \left \{ f_{i - 1,j - (r - l + 1),p, q, 1, y} \right \} \right \} $$$$f_{i, j, l, r, 0, 0} = S_{l, r} + \max_{p\le l \le q\le r} \left \{ \max_{0\le x\le 1} \left \{ f_{i - 1,j - (r - l + 1),p, q, x, 0} \right \} \right \} $$$$f_{i, j, l, r, 1, 0} = S_{l, r} + \begin{cases} f_{i - 1, 0, 0, 0, 1, 0} &{\mathrm{if\ }} j = r - l + 1 > 0\\ \max_{l\le p \le q\le r} \left \{ f_{i - 1,j - (r - l + 1), p, q, 1, 0} \right \} &{\mathrm{if\ }} j > r - l + 1 > 0 \end{cases} $$$$f_{i, j, l, r, 0, 1} = S_{l, r} + \max_{p \le l \le r \le q} \left \{ \max_{0\le x \le 1} \left \{ \max_{0\le y \le 1} \left \{ f_{i - 1, j - (r - l + 1), p, q, x, y} \right \} \right \} \right \} $$

我们发现 $n, m, k$ 很小，因此暴力转移即可。

本题还要求输出方案，我们记录每个阶段从上一个阶段的转移来源最后回溯输出即可。

本题转移不算难想，但是代码实现细节较多，具体见代码。

Code

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define P(C) [C][C * C][C][C][2][2]
#define ft(tp, i, l, r) for (tp i = l; i <= r; i ++)
constexpr int N = 17;
int n, m, k, f P(N), a[N][N];
struct lst {
	int i, j, l, r, x, y;
	lst () : i(0), j(0), l(0), r(0), x(0), y(0) {};
	lst (int a, int b, int c, int d, int e, int f) : 
		i(a), j(b), l(c), r(d), x(e), y(f) {};
} pr P(N), ed;
void dp (int i, int j, int l, int r) {
	i64 sum = 0, len = r - l + 1, dt = 0;
	ft (int, p, l, r) sum += a[i][p];
	if (j == len) dt = f[i - 1][0][0][0][1][0];
	else ft (int, p, l, r) ft(int, q, p, r) if (f[i - 1][j - len][p][q][1][0] > dt) 
		dt = f[i - 1][j - len][p][q][1][0], pr[i][j][l][r][1][0] = lst(i - 1, j - len, p, q, 1,0);
	f[i][j][l][r][1][0] = sum + dt, dt = 0;
	ft(int, p, l, r) ft(int, q, r, m) ft(int, x, 0, 1) if (f[i - 1][j - len][p][q][1][x] > dt) 
		dt = f[i - 1][j - len][p][q][1][x], pr[i][j][l][r][1][1] = lst(i - 1, j - len, p, q, 1,x);
	f[i][j][l][r][1][1] = sum + dt, dt = 0;
	ft(int, p, 1, l) ft(int, q, l, r) ft(int, x, 0, 1) if (f[i - 1][j - len][p][q][x][0] > dt) 
		dt = f[i - 1][j - len][p][q][x][0], pr[i][j][l][r][0][0] = lst(i - 1, j - len, p, q, x,0);
	f[i][j][l][r][0][0] = sum + dt, dt = 0;
	ft(int, p, 1, l) ft(int, q, r, m) ft(int, x, 0, 1) ft(int, y, 0, 1) 
		if (f[i - 1][j - len][p][q][x][y] > dt) dt = f[i - 1][j - len][p][q][x][y], 
			pr[i][j][l][r][0][1] = lst(i - 1, j - len, p, q, x, y);
	f[i][j][l][r][0][1] = sum + dt, dt = 0;
}
void print (lst p) {
	if (p.j == 0) return ;
	print (pr[p.i][p.j][p.l][p.r][p.x][p.y]);
	ft(int, i, p.l, p.r) cout << p.i << ' ' << i << '\n';
}
i64 findans() {
	i64 ans = 0;
	ft(int, i, 1, n) ft(int, l, 1, m) ft(int, r, l, m) 
		ft(int, x, 0, 1) ft(int, y, 0, 1) if (ans < f[i][k][l][r][x][y]) 
			ans = f[i][k][l][r][x][y], ed = lst(i, k, l, r, x, y);
	return ans;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> m >> k;
	ft (int, i, 1, n) ft (int, j, 1, m) cin >> a[i][j];
	ft (int, i, 1, n) ft (int, j, 1, k) 
		ft (int, l, 1, m) ft (int, r, l, m) 
			if (j >= (r - l + 1)) dp(i, j, l, r);
	cout << "Oil : " << findans() << '\n';
	return print(ed), 0;
}