自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 21:49:03，当前版本为作者最后更新于2021-12-13 16:33:44，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

*P3444 [POI2006]ORK-Ploughing

POI 合集。

有趣的思维题。

考虑到最后必然是行或者列被删完，所以我们不妨设行被删完。

接下来，考虑固定左右各删去多少列，即设 $f_{l,r}$ 表示还剩 $l\sim r$ 这些列时，尽量删行之后剩下来的行数的区间 $[p_{l,r},q_{l,r}]$（因为我们要让行尽快被删完）。

区间 $[p,q]$ 是唯一的，反证法可证：假设存在另一个区间 $[p',q']$，不妨设 $q'<q$，那么可以删到 $[p,q']$，与 “尽量删” 的定义矛盾。同理，若 $p<p'$，我们也可以删到 $[p,q]$。$\square$

考虑如何求出 $f_{l,r}$。显然，它要从 $f_{l-1,r}$ 和 $f_{l,r+1}$ 转移过来。如果 $f_{l-1,r}$ 最左边一列能删掉，即 $k\geq \sum_{\\i=p_{l-1,r}}^{q_{l-1,r}}t_{i,j}$，那么 $f_{l,r}$ 继承 $f_{l-1,r}$。同理，若 $f_{l,r+1}$ 最右边一列能删掉，$f_{l,r}$ 也可以继承 $f_{l,r+1}$。任意继承不会影响复杂度：均摊证明时间复杂度是 $\mathcal{O}(nm)$ 的。

同理，假设列被删完再做一遍上述算法即可得到正确答案。

const int N = 2e3 + 5;
int n, m, k, ans = N << 1, row[N][N], c[N][N];
pii f[N][N];
int main(){
	cin >> k >> m >> n;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			c[i][j] = c[i - 1][j] + (row[i][j] = read()), row[i][j] += row[i][j - 1];
	for(int i = 1; i <= n; i++)
		for(int j = i; j <= n; j++)
			f[i][j] = {0, m}; f[1][n] = {1, m};
	for(int len = n; len; len--)
		for(int l = 1, r = len; r <= n; l++, r++) {
			int p = f[l][r].fi, q = f[l][r].se;
			if(!p) continue;
			while(p <= q && c[r][p] - c[l - 1][p] <= k) p++;
			while(p <= q && c[r][q] - c[l - 1][q] <= k) q--;
			if(p > q) cmin(ans, n - len + m);
			if(row[l][q] - row[l][p - 1] <= k) f[l + 1][r] = {p, q};
			if(row[r][q] - row[r][p - 1] <= k) f[l][r - 1] = {p, q};
		}
	for(int i = 1; i <= m; i++)
		for(int j = i; j <= m; j++)
			f[i][j] = {0, n}; f[1][m] = {1, n};
	for(int len = m; len; len--)
		for(int l = 1, r = len; r <= m; l++, r++) {
			int p = f[l][r].fi, q = f[l][r].se;
			if(!p) continue;
			while(p <= q && row[p][r] - row[p][l - 1] <= k) p++;
			while(p <= q && row[q][r] - row[q][l - 1] <= k) q--;
			if(p > q) cmin(ans, n + m - len);
			if(c[q][l] - c[p - 1][l] <= k) f[l + 1][r] = {p, q};
			if(c[q][r] - c[p - 1][r] <= k) f[l][r - 1] = {p, q};
		}
	cout << ans << endl;
	return 0;
}