Dig Dig Dig

· · 题解

参考了官方题解。方便起见，下文不区分 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 个必选，最大代价。转移是显然的：

f_{i,j}=\max_{1\le k< i} \{f_{k,j-1} + c(k,i)\}.

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

c(k,i)=c(k+1,i)+w(k+1,i).

表示不包含 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;
}