「I-country」 I-区域

GitHub跳转原题关系图返回列表

按行扫描的四状态 DP：左端点先减后增、右端点先增后减，连通约束化为矩形前驱区域，用区域最大值把转移压到 O(N·K·M²)。

OJ: roj

题目 ID: 3139

难度:提高+/省选-

标签:

创建: 2026-10-01 19:57

更新: 2026-10-10 11:30

目录

  1. 形式化题目
  2. 正解
    1. 思路
    2. 代码
    3. 复杂度
  3. 总结

形式化题目

给定 N×MN \times M 网格，第 ii 行第 jj 列的权值为 wi,jw_{i,j}。求恰好包含 KK 个格子的凸连通块，使权值和最大，并输出方案。凸连通块需同时满足：

  • 占据连续的若干行，每行取一段连续的列 [Li,Ri][L_i, R_i]，且 Li⩽RiL_i \leqslant R_i；
  • 相邻两行的区间必须相交（连通，中间没有空缺）；
  • 全部左端点 LiL_i 先递减后递增（存在一个谷点），全部右端点 RiR_i 先递增后递减（存在一个峰点），两段都允许非严格单调，退化为纯单调也合法。

样例中 N=2, M=3, K=4N=2,\ M=3,\ K=4：

行\列 1 2 3
1 10 20 30
2 40 2 3

最优方案选第 1 行全部三格与第 2 行第 1 列，权值和 10+20+30+40=10010+20+30+40=100：左端点 1→11 \to 1 保持不增（谷点在末行），右端点 3→13 \to 1 在首行达到峰后递减，相邻行区间 [1,3][1,3] 与 [1,1][1,1] 相交，是合法的凸连通块。

正解

思路

朴素想法是枚举连通块的上下边界，再枚举每一行的左右端点，组合数是指数级的；直接套「枚举每行区间 + 检查单调性」的搜索同样不可行。需要把「端点序列的形状」压缩进状态里。

关键观察：每个端点序列最多只有一个拐点——左端点先降后升、右端点先升后降，各允许在任意一行至多翻转一次方向。于是逐行扫描时，每个端点只需记住 1 位方向信息：

  • fl=0f_l = 0：左端点仍在递减段（还没到谷），fl=1f_l = 1：已过谷转为递增；
  • fr=0f_r = 0：右端点仍在递增段（还没到峰），fr=1f_r = 1：已过峰转为递减。

拐弯只能发生一次，所以 fl,frf_l, f_r 只会从 0 变 1、不会回退，共四种组合。设 F[fl][fr][j][l][r]F[f_l][f_r][j][l][r] 为「扫到当前行、本行取 [l,r][l, r]、恰好用了 jj 格」的最大权值和；连通块可以在任意一行开始（重新从 (0,0)(0,0) 起步），也可以在任意一行结束（答案对所有行取最大）。

转移时枚举本行 [l,r][l, r] 与上一行 [p,q][p, q]。单调方向由当前标志唯一决定（fl=0⇒p⩾lf_l=0 \Rightarrow p \geqslant l，fl=1⇒p⩽lf_l=1 \Rightarrow p \leqslant l，右端点对偶），连通要求 max⁡(l,p)⩽min⁡(r,q)\max(l, p) \leqslant \min(r, q)。两类约束合起来，前驱 (p,q)(p, q) 恰好落在一个规则区域里：

当前 (fl,fr)(f_l, f_r) 允许的上一层状态 前驱 (p,q)(p, q) 合法区域 含义
(0,0)(0,0) (0,0)(0,0) p,q∈[l,r]p, q \in [l, r]（方形） 两端都未拐弯，持续张开
(1,0)(1,0) (0,0),(1,0)(0,0), (1,0) p⩽lp \leqslant l 且 q∈[l,r]q \in [l, r] 左过谷、右仍递增
(0,1)(0,1) (0,0),(0,1)(0,0), (0,1) p∈[l,r]p \in [l, r] 且 q⩾rq \geqslant r 左仍递减、右过峰
(1,1)(1,1) 任意状态 p⩽lp \leqslant l 且 q⩾rq \geqslant r 两端都已拐弯，持续收缩

转移方程为 F′[s][j][l][r]=max⁡(区域s(l,r) 上 F[⋅][j−(r−l+1)][p][q])+sum(i,l,r)F'[s][j][l][r] = \max\big(\text{区域}_s(l,r)\text{ 上 }F[\cdot][j-(r-l+1)][p][q]\big) + \text{sum}(i, l, r)，其中 sum\text{sum} 是本行区间权值和，可用行前缀和 O(1)O(1) 求出。

若对每个状态直接枚举 (p,q)(p, q)，单次转移 O(M2)O(M^2)，总复杂度 O(N⋅K⋅M4)O(N \cdot K \cdot M^4)。但表中的区域都是矩形或方形：矩形区域只需两次一维前后缀 max（先沿 pp 并、再沿 qq 并），方形区域按边长递推「方形 [l,r]=[l, r] = 方形 [l+1,r]∪[l{+}1, r] \cup 第 ll 行 ∪\cup 第 ll 列」。这样每个（行、jj 层、状态组合）只做一次 O(M2)O(M^2) 预处理，之后每次查询 O(1)O(1)，总复杂度降为 O(N⋅K⋅M2)O(N \cdot K \cdot M^2)。

最后回溯方案：逐行冻结 DP 表，从最优终点出发，按同一套「方向 + 相交」约束反查一个等值前驱；找不到前驱即说明本行是连通块首行（多个等值前驱时从大到小扫描，保证输出确定性）。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 油田（Oil Deposits，恰好 k 格）：按行 DP + 四种单调转移的区域最大值 + 回溯方案。
#include <cstdio>
#include <vector>
#include <algorithm>

typedef long long ll;

const ll NEG = -1000000000LL; // 「不可行」哨兵

ll n, m, k;
std::vector<std::vector<ll> > pre; // 行前缀和

// (目标状态层, 可用的上一层状态层, rect_max 的区域种类)
// 状态层 s = fl*2+fr：fl=1 左端点已过谷，fr=1 右端点已过峰
const int COMBOS_DST[4] = {0, 2, 1, 3};
const int COMBOS_KIND[4] = {0, 1, 2, 3};
const int SRC_A[4] = {0, 0, 0, 0};
const int SRC_B[4] = {0, 2, 1, 1};
const int SRC_C[4] = {0, 0, 0, 2};
const int SRC_D[4] = {0, 0, 0, 3};

// 对上一层权值表做区域最大值查询，结果表下标 [l][r]
std::vector<ll> rect_max(std::vector<ll>& a, ll kind) {
    ll mm = m;
    std::vector<ll> res(mm * mm, NEG);
    if (kind == 3) { // 行内右后缀 max（q ≥ r）+ 列向前缀 max（p ≤ l）
        std::vector<ll> t2 = a;
        for (ll p = 0; p < mm; p++) {
            ll b = p * mm, cur = NEG;
            for (ll q = mm - 1; q >= 0; q--) {
                if (t2[b + q] > cur) cur = t2[b + q];
                t2[b + q] = cur;
            }
        }
        for (ll p = 1; p < mm; p++) {
            for (ll q = 0; q < mm; q++) {
                ll u = t2[(p - 1) * mm + q];
                if (u > t2[p * mm + q]) t2[p * mm + q] = u;
            }
        }
        return t2;
    }
    if (kind == 1) { // 先列向并（p ≤ l），再行内从 q=l 起右扫（q ∈ [l, r]）
        std::vector<ll> e = a;
        for (ll p = 1; p < mm; p++) {
            for (ll q = 0; q < mm; q++) {
                ll u = e[(p - 1) * mm + q];
                if (u > e[p * mm + q]) e[p * mm + q] = u;
            }
        }
        for (ll l = 0; l < mm; l++) {
            ll b = l * mm, cur = NEG;
            for (ll q = l; q < mm; q++) {
                if (e[b + q] > cur) cur = e[b + q];
                res[b + q] = cur;
            }
        }
        return res;
    }
    if (kind == 2) { // 先行内右后缀（q ≥ r），再列内从 p=r 往上扫（p ∈ [l, r]）
        std::vector<ll> g = a;
        for (ll p = 0; p < mm; p++) {
            ll b = p * mm, cur = NEG;
            for (ll q = mm - 1; q >= 0; q--) {
                if (g[b + q] > cur) cur = g[b + q];
                g[b + q] = cur;
            }
        }
        for (ll r = 0; r < mm; r++) {
            ll cur = NEG;
            for (ll p = r; p >= 0; p--) {
                if (g[p * mm + r] > cur) cur = g[p * mm + r];
                res[p * mm + r] = cur;
            }
        }
        return res;
    }
    // kind 0：方形 [l, r]×[l, r]，行 max + 列 max 后按边长递推
    std::vector<ll> rp = a;
    for (ll p = 0; p < mm; p++) {
        ll b = p * mm;
        for (ll q = 1; q < mm; q++) {
            if (rp[b + q - 1] > rp[b + q]) rp[b + q] = rp[b + q - 1];
        }
    }
    std::vector<ll> cp(mm * mm, NEG);
    for (ll l = 0; l < mm; l++) {
        ll cur = NEG;
        for (ll p = l; p < mm; p++) {
            if (a[p * mm + l] > cur) cur = a[p * mm + l];
            cp[p * mm + l] = cur;
        }
    }
    for (ll d = 0; d < mm; d++) { // d = r - l，小边长先算
        for (ll l = 0; l + d < mm; l++) {
            ll r = l + d;
            ll v = rp[l * mm + r];
            if (cp[r * mm + l] > v) v = cp[r * mm + l];
            if (d) {
                ll u = res[(l + 1) * mm + r];
                if (u > v) v = u;
            }
            res[l * mm + r] = v;
        }
    }
    return res;
}

struct Pick {
    ll row, l, r;
};

int main() {
    if (scanf("%lld %lld %lld", &n, &m, &k) != 3) return 0; // 空输入安全返回
    std::vector<std::vector<ll> > w(n, std::vector<ll>(m, 0));
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < m; j++) {
            scanf("%lld", &w[i][j]);
        }
    }

    if (k == 0) { // 空连通块
        printf("Oil : 0\n");
        return 0;
    }

    pre.assign(n, std::vector<ll>(m + 1, 0));
    for (ll i = 0; i < n; i++) {
        for (ll c = 0; c < m; c++) {
            pre[i][c + 1] = pre[i][c] + w[i][c];
        }
    }

    ll W = m * m;
    ll k1 = k + 1;
    std::vector<ll> slots, sizes;
    for (ll l = 0; l < m; l++) {
        for (ll r = l; r < m; r++) {
            slots.push_back(l * m + r);
            sizes.push_back(r - l + 1);
        }
    }
    ll S = (ll)slots.size();

    // 四层 DP 表，下标 [s][j*W + slot]
    std::vector<std::vector<ll> > F(4, std::vector<ll>(k1 * W, NEG));
    // 每行结束后冻结一张表，供最后回溯方案
    std::vector<ll> hist((size_t)n * 4 * k1 * W, 0);
    ll best = NEG;
    ll best_row = 0, best_state = 0, best_slot = 0;

    std::vector<ll> A(W, 0), R;
    std::vector<ll> seg_row(S, 0);

    for (ll i = 0; i < n; i++) {
        std::vector<std::vector<ll> > newF(4, std::vector<ll>(k1 * W, NEG));
        for (ll t = 0; t < S; t++) {
            ll l = slots[t] / m, r = slots[t] % m;
            seg_row[t] = pre[i][r + 1] - pre[i][l];
        }
        ll jtop = i * m;
        if (jtop > k - 1) jtop = k - 1;

        for (ll ci = 0; ci < 4; ci++) {
            ll dst_s = COMBOS_DST[ci], kind = COMBOS_KIND[ci];
            std::vector<ll> dst = newF[dst_s];
            for (ll jp = 1; jp <= jtop; jp++) {
                ll base = jp * W;
                for (ll t = 0; t < W; t++) A[t] = F[SRC_A[ci]][base + t];
                if (ci == 1) { // (1,0) ← (0,0)/(1,0)
                    for (ll t = 0; t < W; t++) {
                        ll x = F[SRC_B[ci]][base + t];
                        if (x > A[t]) A[t] = x;
                    }
                } else if (ci == 2) { // (0,1) ← (0,0)/(0,1)
                    for (ll t = 0; t < W; t++) {
                        ll x = F[SRC_B[ci]][base + t];
                        if (x > A[t]) A[t] = x;
                    }
                } else if (ci == 3) { // (1,1) ← 任意
                    for (ll s = 1; s < 4; s++) {
                        for (ll t = 0; t < W; t++) {
                            ll x = F[s][base + t];
                            if (x > A[t]) A[t] = x;
                        }
                    }
                }
                ll mx = A[0];
                for (ll t = 1; t < W; t++) {
                    if (A[t] > mx) mx = A[t];
                }
                if (mx <= NEG / 2) continue; // 该层源状态全不可达
                R = rect_max(A, kind);
                for (ll t = 0; t < S; t++) {
                    ll jn = jp + sizes[t];
                    if (jn > k) continue;
                    ll v = R[slots[t]] + seg_row[t];
                    if (v <= NEG / 2) continue;
                    if (v > newF[dst_s][jn * W + slots[t]]) {
                        newF[dst_s][jn * W + slots[t]] = v;
                    }
                }
            }
        }
        // 本行作为连通块首行：单调状态回到 (0,0)
        for (ll t = 0; t < S; t++) {
            if (sizes[t] <= k) {
                ll slot = sizes[t] * W + slots[t];
                if (seg_row[t] > newF[0][slot]) newF[0][slot] = seg_row[t];
            }
        }
        // 连通块可以在任意一行结束：记录恰 k 格的历史最优
        ll base_k = k * W;
        for (ll s = 0; s < 4; s++) {
            for (ll t = 0; t < S; t++) {
                ll v = newF[s][base_k + slots[t]];
                if (v > best) {
                    best = v;
                    best_row = i;
                    best_state = s;
                    best_slot = slots[t];
                }
            }
        }
        for (ll s = 0; s < 4; s++) {
            for (ll t = 0; t < k1 * W; t++) {
                hist[((size_t)i * 4 + s) * k1 * W + t] = newF[s][t];
            }
        }
        F.swap(newF);
    }

    std::vector<Pick> picked;
    ll end_row = best_row, s = best_state, slot = best_slot;
    ll l = slot / m, r = slot % m;
    ll j = k;
    while (true) {
        Pick pk;
        pk.row = end_row;
        pk.l = l;
        pk.r = r;
        picked.push_back(pk);
        ll sz = r - l + 1;
        ll jp = j - sz;
        ll fl = s >> 1, fr = s & 1;
        ll want = hist[((size_t)end_row * 4 + s) * k1 * W + j * W + slot]
                  - (pre[end_row][r + 1] - pre[end_row][l]);
        bool found = false;
        ll ns = 0, nl = 0, nr = 0;
        if (end_row > 0) {
            for (ll s0 = 0; s0 < 4; s0++) {
                if ((s0 >> 1) > fl || (s0 & 1) > fr) continue; // 拐过的弯不能回退
                for (ll p = m - 1; p >= 0; p--) {
                    if (fl == 0 && p < l) continue;
                    if (fl == 1 && p > l) continue;
                    for (ll q = m - 1; q >= 0; q--) {
                        if (fr == 0 && q > r) continue;
                        if (fr == 1 && q < r) continue;
                        if (q < l || p > r || p > q) continue;
                        ll hv = hist[((size_t)(end_row - 1) * 4 + s0) * k1 * W + jp * W + p * m + q];
                        if (hv == want) {
                            found = true;
                            ns = s0;
                            nl = p;
                            nr = q;
                            break;
                        }
                    }
                    // 与 Python 的 `if nxt: break` 一致：可能由更早的 s0 置位
                    if (found) break;
                }
            }
        }
        if (!found) break; // 没有前驱行：本行即连通块首行
        s = ns;
        l = nl;
        r = nr;
        slot = l * m + r;
        j = jp;
        end_row = end_row - 1;
    }

    std::reverse(picked.begin(), picked.end());
    printf("Oil : %lld\n", best);
    for (size_t t = 0; t < picked.size(); t++) {
        for (ll c = picked[t].l; c <= picked[t].r; c++) {
            printf("%lld %lld\n", picked[t].row + 1, c + 1);
        }
    }
    return 0;
}
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 20:42
# update_at: 2026-10-01 20:42

import sys
from array import array

NEG = -10**9  # 「不可行」哨兵：比任何合法权值和都小一个数量级


def rect_max(a: list[int], kind: int) -> list[int]:
    """对上一层 (p, q) 权值表做区域最大值查询，结果表下标 [l][r] 即当前行取 [l, r] 的最优前驱值。

    四种 kind 对应四种单调转移允许的前驱区域（p=上一行左端点, q=上一行右端点）：
    kind 0：方形 p, q ∈ [l, r]（两端点都还在「先减/先增」段）；
    kind 1：p ≤ l 且 q ∈ [l, r]（左端点已过谷, 右端点仍在递增段）；
    kind 2：p ∈ [l, r] 且 q ≥ r（左端点仍在递减段, 右端点已过峰）；
    kind 3：p ≤ l 且 q ≥ r（两端点都已拐弯, 持续收缩）。
    """
    m = int(len(a) ** 0.5)
    if kind == 3:  # 两次单向扫描：行内右后缀 max（q ≥ r）+ 列向前缀 max（p ≤ l）
        res = a[:]
        for p in range(m):
            b, t = p * m, NEG
            for q in range(m - 1, -1, -1):  # 行内从右往左并
                if res[b + q] > t:
                    t = res[b + q]
                res[b + q] = t
        for p in range(1, m):
            for q in range(m):
                u = res[(p - 1) * m + q]
                if u > res[p * m + q]:
                    res[p * m + q] = u
        return res
    if kind == 1:  # 先列向并（p ≤ l），再行内从 q=l 起右扫（q ∈ [l, r]）
        e = a[:]
        for p in range(1, m):
            for q in range(m):
                u = e[(p - 1) * m + q]
                if u > e[p * m + q]:
                    e[p * m + q] = u
        res = [NEG] * (m * m)
        for l in range(m):
            b, t = l * m, NEG
            for q in range(l, m):
                if e[b + q] > t:
                    t = e[b + q]
                res[b + q] = t
        return res
    if kind == 2:  # 先行内右后缀（q ≥ r），再列内从 p=r 往上扫（p ∈ [l, r]）
        g = a[:]
        for p in range(m):
            b, t = p * m, NEG
            for q in range(m - 1, -1, -1):
                if g[b + q] > t:
                    t = g[b + q]
                g[b + q] = t
        res = [NEG] * (m * m)
        for r in range(m):
            t = NEG
            for p in range(r, -1, -1):
                if g[p * m + r] > t:
                    t = g[p * m + r]
                res[p * m + r] = t
        return res
    # kind 0：方形 [l, r]×[l, r]。行 max + 列 max 后按边长递推：
    # 方形 [l, r] = 方形 [l+1, r] ∪ 第 l 行 ∪ 第 l 列
    rp = a[:]
    for p in range(m):
        b = p * m
        for q in range(1, m):
            u = rp[b + q - 1]
            if u > rp[b + q]:
                rp[b + q] = u
    cp = [NEG] * (m * m)  # 列向只从 p=l 起并：p<l 的槽是合法状态，不能混进方形
    for l in range(m):
        t = NEG
        for p in range(l, m):
            x = a[p * m + l]
            if x > t:
                t = x
            cp[p * m + l] = t
    res = [NEG] * (m * m)
    for d in range(m):  # d = r - l，小边长先算
        for l in range(m - d):
            r = l + d
            v = rp[l * m + r]  # 第 l 行 q ∈ [l, r]（q<l 的槽 p>q 恒为哨兵）
            c = cp[r * m + l]  # 第 l 列 p ∈ [l, r]
            if c > v:
                v = c
            if d:
                u = res[(l + 1) * m + r]
                if u > v:
                    v = u
            res[l * m + r] = v
    return res


# (目标状态层, 可用的上一层状态层, rect_max 的区域种类)
# 状态层 s = fl*2+fr：fl=1 表示左端点已过谷（开始递增），fr=1 表示右端点已过峰（开始递减）
COMBOS = (
    (0, (0,), 0),               # (0,0) ← (0,0)        两端都未拐弯
    (2, (0, 2), 1),             # (1,0) ← (0,0)/(1,0)  左过谷、右仍递增
    (1, (0, 1), 2),             # (0,1) ← (0,0)/(0,1)  左仍递减、右过峰
    (3, (0, 1, 2, 3), 3),       # (1,1) ← 任意         两端都已拐弯，持续收缩
)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m, k = next(data), next(data), next(data)
    w = [[next(data) for _ in range(m)] for _ in range(n)]

    if k == 0:  # 空连通块
        print("Oil : 0")
        return

    pre = [[0] * (m + 1) for _ in range(n)]  # 行前缀和：区间 [l, r] 和 = pre[i][r+1] - pre[i][l]
    for i in range(n):
        for c, x in enumerate(w[i]):
            pre[i][c + 1] = pre[i][c] + x

    segs = [(l, r) for l in range(m) for r in range(l, m)]  # 合法列区间，扁平槽位 W = l*m + r
    slots = [l * m + r for l, r in segs]
    sizes = [r - l + 1 for l, r in segs]
    m2, k1 = m * m, k + 1

    # 四层 DP 表，下标 [s][j*m2 + W]：已用 j 格、当前行取该区间、单调状态 s 的最大权值和
    F = [[NEG] * (k1 * m2) for _ in range(4)]
    hist: list[tuple] = []  # 每行结束后冻结一张表，供最后回溯方案
    best, best_state = NEG, (0, 0, 0)

    for i in range(n):
        newF = [[NEG] * (k1 * m2) for _ in range(4)]
        seg_row = [pre[i][r + 1] - pre[i][l] for l, r in segs]  # 本行每个区间的权值和
        jtop = min(k - 1, i * m)  # 上一层最多 i*m 格；且 j + size ≤ k ⇒ j ≤ k-1
        for dst_s, srcs, kind in COMBOS:
            dst = newF[dst_s]
            for jp in range(1, jtop + 1):
                base = jp * m2
                A = F[srcs[0]][base:base + m2]  # 可用源层逐槽取 max 合成一张表
                for s in srcs[1:]:
                    B = F[s]
                    for t in range(m2):
                        x = B[base + t]
                        if x > A[t]:
                            A[t] = x
                if max(A) <= NEG // 2:  # 该层源状态全不可达
                    continue
                R = rect_max(A, kind)
                for t, W in enumerate(slots):
                    jn = jp + sizes[t]
                    if jn > k:
                        continue
                    v = R[W] + seg_row[t]
                    if v <= NEG // 2:
                        continue
                    slot = jn * m2 + W
                    if v > dst[slot]:
                        dst[slot] = v
        # 本行作为连通块首行：单调状态回到 (0,0)，之前各行均为 0 格
        for t, W in enumerate(slots):
            if sizes[t] <= k:
                slot = sizes[t] * m2 + W
                if seg_row[t] > newF[0][slot]:
                    newF[0][slot] = seg_row[t]
        # 连通块可以在任意一行结束：记录「恰 k 格」的历史最优
        base_k = k * m2
        for s in range(4):
            layer = newF[s]
            for W in slots:
                v = layer[base_k + W]
                if v > best:
                    best, best_state = v, (i, s, W)
        hist.append(tuple(array("i", layer) for layer in newF))
        F = newF

    # 回溯：从最优终点逐行往回找一个取到该值的前驱，找不到即说明本行是首行
    end_row, s, W = best_state
    l, r = divmod(W, m)
    j = k
    picked: list[tuple[int, int, int]] = []
    while True:
        picked.append((end_row, l, r))
        size = r - l + 1
        jp = j - size
        fl, fr = s >> 1, s & 1
        want = hist[end_row][s][j * m2 + W] - (pre[end_row][r + 1] - pre[end_row][l])
        nxt = None
        if end_row > 0:
            prev = hist[end_row - 1]
            for s0 in range(4):
                if (s0 >> 1) > fl or (s0 & 1) > fr:  # 拐过的弯不能回退
                    continue
                for p in range(m - 1, -1, -1):  # 多个等优前驱时从大到小扫描
                    if (fl == 0 and p < l) or (fl == 1 and p > l):  # 左端点单调方向
                        continue
                    for q in range(m - 1, -1, -1):
                        if (fr == 0 and q > r) or (fr == 1 and q < r):  # 右端点单调方向
                            continue
                        if q < l or p > r or p > q:  # 相邻行相交（连通）且前驱区间合法
                            continue
                        if prev[s0][jp * m2 + p * m + q] == want:
                            nxt = (s0, p, q)
                            break
                    if nxt:
                        break
        if nxt is None:  # 没有前驱行：本行即连通块首行
            break
        s, l, r = nxt
        W = l * m + r
        j, end_row = jp, end_row - 1

    picked.reverse()  # 输出按行号、列号升序
    out = [f"Oil : {best}"]
    out += [f"{ri + 1} {c + 1}" for ri, l, r in picked for c in range(l, r + 1)]
    print("\n".join(out))


if __name__ == "__main__":
    solve()

复杂度

  • 时间：每个（行、jj 层、状态组合）做一次 O(M2)O(M^2) 区域预处理与 O(1)O(1) 查询，共 O(N⋅K⋅M2)O(N \cdot K \cdot M^2)；N,M⩽15N, M \leqslant 15、K⩽225K \leqslant 225 时约为 10710^7 量级。
  • 空间：两层工作表各 4×(K+1)×M24 \times (K{+}1) \times M^2 个整数，逐行存档用于回溯共 N×4×(K+1)×M2N \times 4 \times (K{+}1) \times M^2，约 12 MB。

总结

  • 每个端点序列只有一个拐点：把「是否已拐弯」压成 2 bit 方向状态，四种组合即覆盖全部合法轮廓。
  • 单调方向与相邻行相交两类约束叠加后，前驱集合恰好是矩形/方形，转移转化为区域最大值查询；一维前后缀与边长递推把单层预处理压到 O(M2)O(M^2)。
  • jj 维度（恰好 KK 格）按本行宽度平移对齐；连通块的起点用「重新起步」状态、终点对所有行取最大处理。