自动搬运

查看原文

来自洛谷，原作者为

	冷却心 111

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

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

以下是正文

参考了官方题解。方便起见，下文不区分 $n,m$。

对于一个石油连通块，我们记其最左侧在第 $l$ 列，最右侧在第 $r$ 列，那么在 $[l,r]$ 中任选一列就会造成贡献，所以我们把每个连通块缩成一个线段 $[l,r]$ 附带石油总和作为权值，问题变为：

给定 $q$ 条线段 $[l_i,r_i]$ 附加 $s_i$ 的权值，对每个 $i \in [n]$ 求出在 $1$ 到 $n$ 中选择 $i$ 个整点，使得和这些整点有交的线段的权值总和最大，求出最大权值和。$1\le l_i\le r_i\le n$，$q$ 是平方级别，但是保证线段长度之和至多 $n^2$。

考虑 dp。记状态 $f_{i,j}$ 表示在前 $i$ 列中选了 $j$ 个，其中第 $i$ 个必选，最大代价。转移是显然的：

其中 $c(k,i)$ 表示不包含 $k$ 但是包含 $i$ 的线段权值和。$c(k,i)$ 不是很好求，我们先求 $w(i,j)$ 表示以 $i$ 为左端点并且包含 $j$ 的线段权值和。这个是好求的，遍历每条线段即可。然后有转移：

表示不包含 $k$ 但是包含 $i$ 的线段权值和，由不包含 $k+1$ 但是包含 $i$ 的线段以及以 $k+1$ 为左端点且包含 $i$ 的线段组成。

然后做完了，这样 $\mathcal O(n^2)$ 求 $c,w$，$\mathcal O(n^3)$ dp。

然后考虑优化。先给出结论，dp 状态具有决策单调性，即记 $p(i,j)$ 表示 $f_{i,j}$ 的最优决策点，那么保证 $p(i,j)\le p(i+1,j)$。于是我们按 $j$ 分层转移，每次转移用分治维护就好了。时间复杂度 $\mathcal O(n^2\log n)$。

决策单调性的不严谨证明：

首先当 $p(i,j)$ 不存在，也就是 $i<j$ 的时候结论显然成立，不再讨论。

为了便于书写记 $p=p(i,j),q=p(i+1,j)$，考虑反证法，设 $p > q$，那么我们有：

$$\begin{aligned} f_{i,j}=f_{p,j-1}+c(p,i)&>f_{q,j-1}+c(q,i),\\ f_{i+1,j}=f_{q,j-1}+c(q,i+1)&\ge f_{p,j-1}+c(p,i+1),\\ \end{aligned} $$

上下两式相加化简得到：

$$c(p,i)+c(q,i+1)>c(q,i)+c(p,i+1).$$

我们记 $g(i,j)$ 表示以 $i$ 结尾且不包含 $j$ 的线段权值和，那么我们可以得到一个类似的关于 $c$ 的递推式：

$$c(i,j+1)=c(i,j)-g(j,i).$$

那么：

$$\begin{aligned} c(p,i+1)&=c(p,i)-g(i,p),\\ c(q,i+1)&=c(q,i)-g(i,q). \end{aligned} $$

代入不等式化简得到 $g(i,p)>g(i,q)$。但是 $g(i,j)$ 固定 $i$，当 $j$ 越小的时候显然 $g$ 越大，而 $p>q$ 却满足 $g(i,p)>g(i,q)$，所以矛盾，决策单调性得证。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2e3 + 10;
int n, m; char S[N][N]; 
bool vis[N][N]; int cur, mn, mx;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
void DFS(int x, int y) {
	mn = min(mn, y); mx = max(mx, y); cur += (S[x][y] - '0'); vis[x][y] = 1;
	for (int i = 0; i < 4; i ++) {
		int a = x + dx[i], b = y + dy[i];
		if (a >= 1 && a <= n && b >= 1 && b <= m && !vis[a][b] && S[a][b] != '.') DFS(a, b);
	} return ;
}
struct Seg { int l, r, k; } seg[N * N]; int tot;
vector<int> vec[N]; int W[N][N], cost[N][N], DP[N][N];

void Solve(int l, int r, int pl, int pr, int id) {
	if (l > r || pl > pr) return ;
	int mid = (l + r) >> 1, k = pl;
	for (int i = pl + 1; i <= min(pr, mid - 1); i ++)
		if (DP[i][id - 1] + cost[i][mid] > DP[k][id - 1] + cost[k][mid]) k = i;
	DP[mid][id] = DP[k][id - 1] + cost[k][mid];
	Solve(l, mid - 1, pl, k, id); Solve(mid + 1, r, k, pr, id);
}

int main() {
	freopen(".in", "r", stdin); freopen(".out", "w", stdout);
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m; for (int i = 1; i <= n; i ++) cin >> (S[i] + 1);
	for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++)
		if (S[i][j] != '.' && !vis[i][j]) { 
			mn = m + 1, cur = mx = 0; DFS(i, j); seg[++ tot] = {mn, mx, cur};
			vec[mn].push_back(tot);
		}
	for (int i = 1; i <= m; i ++)
		for (int x : vec[i]) for (int j = seg[x].l; j <= seg[x].r; j ++)
			W[i][j] += seg[x].k, DP[j][1] += seg[x].k;
	for (int i = m; i >= 1; i --)
		for (int j = i + 1; j <= m; j ++) 
			cost[i][j] = cost[i + 1][j] + W[i + 1][j];
	for (int i = 2; i <= m; i ++) Solve(i, m, 1, m, i);
	for (int i = 1; i <= m; i ++) {
		int res = 0;
		for (int j = 1; j <= m; j ++) res = max(res, DP[j][i]);
		cout << res << "\n";
	}
	return 0;
}