景中人

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

矩形底边都贴在 y=0,故存在「底边区间相离或包含」的最优解;按此性质对最左列做区间 DP,按高度分层转移,O(nn³m) 解决。

OJ: roj

题目 ID: 1769

难度:提高+/省选-

标签:动态规划区间DP贪心性质python

创建: 2026-10-08 01:09

更新: 2026-10-08 01:09

形式化题目

平面上有 nn 个点 (xi,yi)(x_i, y_i),满足 0⩽xi⩽3×1060 \leqslant x_i \leqslant 3 \times 10^6、1⩽yi⩽S⩽2×1051 \leqslant y_i \leqslant S \leqslant 2 \times 10^5。 要用若干个矩形盖住所有点,每个矩形都必须满足两条限制:

  1. 一条边贴在直线 y=0y = 0 上,即矩形形如 [a,b]×[0,h][a, b] \times [0, h](a⩽ba \leqslant b,h⩾0h \geqslant 0);
  2. 面积不超过 SS,即 (b−a) h⩽S(b - a)\,h \leqslant S。

点 (x,y)(x, y) 被这个矩形盖住,当且仅当

a⩽x⩽b且y⩽h.a \leqslant x \leqslant b \quad \text{且} \quad y \leqslant h .

求盖住全部点所需矩形数的最小值。多组数据:第一行 TT,每组先给 n,Sn, S,再给 nn 行 xi yix_i\ y_i; 每组输出一行答案。数据规模 T⩽10T \leqslant 10、n⩽100n \leqslant 100。

正解

思路

第一步:把"覆盖"翻译成两个方向的约束。

矩形 [a,b]×[0,h][a,b] \times [0,h] 的面积是宽乘高,所以

  • 高度取定时,宽度上限是 ⌊S/h⌋\lfloor S/h \rfloor;
  • 宽度取定时,高度上限是 ⌊S/w⌋\lfloor S/w \rfloor。

这两句话是后面所有剪枝的来源:矩形越宽,允许的高度就越矮。

第二步:同一横坐标只留最高点。 由覆盖判据,矩形盖住 (x,y)(x,y) 只看两件事:xx 是否落在底边区间内、 yy 是否不超过高度。于是同一列 xx 上的所有点里,只有最高的那个点有用——它被盖住,整列就都被盖住了。 压缩后得到 nnnn 列,第 tt 列的横坐标 xstxs_t、最高点高度 HtH_t。再把高度离散化成排名 rank⁡t∈[1,m]\operatorname{rank}_t \in [1, m](mm 是不同高度的个数,排名越大越高),因为后面的转移只关心 “谁比谁高”。

朴素做法与瓶颈。 一个自然的想法是枚举每个点属于哪个矩形,O(2n)O(2^n) 级别,n⩽100n \leqslant 100 时直接爆掉; 也可以枚举所有"有用矩形"(底边端点取在某两列的横坐标、高度取某个 HtH_t,共 O(n2m)O(n^2m) 个)再做集合覆盖, 同样是 NPC 级别的暴力。真正的问题是矩形之间会互相"顺带覆盖",把点集切得七零八落, 不能简单地按 xx 从左到右贪心。

一个诱人但错误的简化。 看到"矩形底边贴 y=0y=0",很容易想到:取最高的点 PP,盖它的矩形高度必然是 HPH_P、宽度上限 ⌊S/HP⌋\lfloor S/H_P \rfloor,这个矩形顺手把横坐标落在它底边内、高度不超过 HPH_P 的点全灭了, 于是问题被切成左右两个独立子问题。这个简化是错的。 反例:

(0,1), (50,100), (100,1),S=100.(0,1),\ (50,100),\ (100,1), \qquad S = 100 .

按"最高点"分治:盖 (50,100)(50,100) 的矩形宽度至多 11,切完之后左右各剩一个点,一共 33 个矩形。 但答案是 22:[0,100]×[0,1][0,100] \times [0,1](面积 100100)盖住左右两个矮点, [50,51]×[0,100][50,51] \times [0,100](面积 100100)盖住高点。错因在于又矮又宽的矩形可以横跨两个子问题, "高矩形把区间切断"这个直觉只对高矩形内部成立,对外面不成立。

第三步(关键性质):存在最优解,任意两个矩形的底边区间"相离或包含"。

任取两个底边区间相交但不包含的矩形,设为 [a1,b1]×[0,h1][a_1,b_1] \times [0,h_1] 与 [a2,b2]×[0,h2][a_2,b_2] \times [0,h_2], 其中 a1<a2⩽b1<b2a_1 < a_2 \leqslant b_1 < b_2。

  • 若 h1⩾h2h_1 \geqslant h_2:把矩形 2 截短成 [b1,b2]×[0,h2][b_1, b_2] \times [0, h_2]。它原本盖住而新位置盖不到的点, 横坐标都在 [a2,b1][a_2, b_1] 内、高度不超过 h2⩽h1h_2 \leqslant h_1,已经落在矩形 1 里了。
  • 若 h1<h2h_1 < h_2:把矩形 1 截短成 [a1,a2]×[0,h1][a_1, a_2] \times [0, h_1]。它原本盖住而新位置盖不到的点, 横坐标都在 [a2,b1][a_2, b_1] 内、高度不超过 h1<h2h_1 < h_2,已经落在矩形 2 里了。

两种情形都只把某个矩形变窄(面积更小、合法性不变)、矩形数不变,且不会让任何点失去覆盖。 每次操作后区间总长度严格减少,反复执行即可得到"两两相离或包含"的解,故该性质成立。

第四步:按"最左列"分解。 在这样一组解里,取覆盖最左待覆盖列 ii 的那个矩形,若它被别的矩形包含, 就换成包含它的那个,直到取到极大的那个,记作 RR。由第三步的性质:

  • 任何与 RR 的底边区间相交的矩形,要么含于 RR、要么包含 RR;后者与 RR 的极大性矛盾, 所以它们全部含于 RR(这也说明 RR 是最外层的)。
  • 于是 RR 的底边区间把问题切成互不相干的两块:RR 内部,和 RR 右侧。

RR 覆盖着第 ii 列的点,所以它的底边可以左缩到 xsixs_i;右端缩到它盖住的最后一列 qq 的横坐标 xsqxs_q, 即 RR 可取 [xsi,xsq]×[0,h][xs_i, xs_q] \times [0, h],hh 取宽度允许的最大值

ymx⁡(i,q)=max⁡{ Ht:Ht⋅(xsq−xsi)⩽S }\operatorname{ymx}(i,q) = \max \{\, H_t : H_t \cdot (xs_q - xs_i) \leqslant S \,\}

(宽度为 00 时不受限制,取最高档 mm)。高度取满不会让面积超标,只会多盖点,永远不劣。

第五步:转移。 设 dp[k][i][j]dp[k][i][j] 表示盖住列 i…ji \dots j 中高度排名 ⩾k\geqslant k 的点所需的最少矩形数。 按最左列分解,分两种情况:

  • rank⁡i<k\operatorname{rank}_i < k:第 ii 列没有待覆盖的点,整列跳过,dp[k][i][j]=dp[k][i+1][j]dp[k][i][j] = dp[k][i+1][j]。
  • 否则第 ii 列最高点必须被盖住,它就是上面那个 RR 要负责的点,于是
dp[k][i][j]=min⁡q(  g[i][q]+dp[k][q+1][j]  ),g[i][q]=1+dp[ymx⁡(i,q)+1][i][q], dp[k][i][j] = \min_{q}\Bigl(\; g[i][q] + dp[k][q+1][j] \;\Bigr), \qquad g[i][q] = 1 + dp[\operatorname{ymx}(i,q)+1][i][q],

其中 qq 取遍 [ i, min⁡(limQ⁡i, j) ][\,i,\ \min(\operatorname{limQ}_i,\ j)\,]:

  • 底边 [xsi,xsq][xs_i, xs_q] 必须盖得住第 ii 列最高点,即 ymx⁡(i,q)⩾rank⁡i\operatorname{ymx}(i,q) \geqslant \operatorname{rank}_i。 因为 ymx⁡\operatorname{ymx} 随 qq 单调不增(底边越宽、允许高度越矮),这类 qq 正好是一个前缀, 右端点记作 limQ⁡i\operatorname{limQ}_i,扫一遍就能求出。
  • q⩽jq \leqslant j 可以放心剪掉:q>jq > j 时矩形盖的列更多、允许的高度更低,g[i][j]⩽g[i][q]g[i][j] \leqslant g[i][q] 恒成立,留着也不会更优。

g[i][q]g[i][q] 的含义是"底边 [xsi,xsq][xs_i, xs_q] 的最外层矩形 + 它内部剩下的高点": 矩形盖住列 i…qi \dots q 中高度不超过 ymx⁡\operatorname{ymx} 的点,剩下的只能是同一批列里更高的点, 它们必然被含于 RR 的矩形处理,正是 dp[ymx⁡+1][i][q]dp[\operatorname{ymx}+1][i][q]。

第六步:计算顺序。 转移里 dp[ymx⁡+1][⋅][⋅]dp[\operatorname{ymx}+1][\cdot][\cdot] 的阈值 ymx⁡+1>k\operatorname{ymx}+1 > k, 所以 kk 从 mm 降到 11 逐层算;同层内 dp[k][q+1][j]dp[k][q+1][j] 的 q+1>iq+1 > i,所以 ii 从右往左扫。 答案就是 dp[1][1][nn]dp[1][1][nn](阈值 11 = 所有点都要盖)。

用样例核对:n=6,S=4n=6,S=4,点为 (2,1),(4,1),(5,1),(5,4),(7,1),(6,4)(2,1),(4,1),(5,1),(5,4),(7,1),(6,4), 压缩成 5 列 x=2,4,5,6,7x = 2,4,5,6,7,高度排名 1,1,2,2,11,1,2,2,1,m=2m=2。高度上限 44 只允许宽度 11, 所以盖住两个高点 (5,4),(6,4)(5,4),(6,4) 的矩形只能是 [5,6]×[0,4][5,6] \times [0,4],剩下的左半两列与右半一列各用一个矩形, 共 33 个,与样例输出一致。

代码

Python 版:

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-08 01:09
# update_at: 2026-10-08 01:09

import sys

INF = 10 ** 9  # 转移里"不可能"的代价,最大答案不超过列数 100

# 类型别名(Python 3.12+ 的 type 语句):dp 表按 [行][列] 索引
type Grid = list[list[int]]


def compress(points: list[tuple[int, int]]) -> tuple[list[int], list[int], list[int]]:
    """列压缩:同一横坐标只留最高点,返回 (各列横坐标, 各列最高点的高度排名, 排名->高度)。

    矩形 [a,b] x [0,h] 覆盖点 (x,y) 当且仅当 a <= x <= b 且 y <= h,
    所以同一列里只有最高的点有用,矮点被它代表。
    """
    top: dict[int, int] = {}
    for x, y in points:
        if y > top.get(x, 0):  # 题面保证 y >= 1,所以 0 可以当"还没有点"的哨兵
            top[x] = y
    xs = sorted(top)
    hval = sorted(set(top.values()))
    rank_of = {h: r for r, h in enumerate(hval, 1)}  # 高度 -> 排名,1 最矮
    return xs, [rank_of[top[x]] for x in xs], hval


def min_rects(xs: list[int], rank: list[int], hval: list[int], S: int) -> int:
    """最少矩形数。状态 dp[k][i][j]:覆盖列 i..j 中高度排名 >= k 的点所需的最少矩形数。

    取最左的待覆盖列 i,覆盖它的最外层矩形底边是 [xs[i], xs[q]],高度取宽度允许的最大值;
    该矩形把列 i..q 中高度不超过它的点全部吃掉,剩余点只可能是
      · 列 i..q 中更高的点 —— 由嵌在它内部的矩形处理,即 dp[ymx+1][i][q];
      · 列 q+1..j 的点 —— 与它相离,即 dp[k][q+1][j]。
    于是 dp[k][i][j] = min_q ( g[i][q] + dp[k][q+1][j] ),g[i][q] = 1 + dp[ymx+1][i][q]。
    """
    n = len(xs)
    m = len(hval)
    ymx: Grid = [[m] * n for _ in range(n)]  # ymx[i][q]:底边 i..q 时允许的最大高度排名
    lim = [0] * n                            # lim[i]:仍盖得住第 i 列最高点的最大 q
    for i in range(n):
        h = m
        lim[i] = i
        for q in range(i + 1, n):
            while h and hval[h - 1] * (xs[q] - xs[i]) > S:
                h -= 1                       # 底边变宽,允许的高度只会更矮
            ymx[i][q] = h
            if h >= rank[i]:                 # 盖得住第 i 列最高点,它才配当最外层矩形
                lim[i] = q

    prev: Grid = [[0] * (n + 1) for _ in range(n + 1)]  # 第 k+1 层,初值即 dp[m+1] 全 0
    g: Grid = [[0] * n for _ in range(n)]               # g[i][q] = 1 + dp[ymx[i][q]+1][i][q]
    for k in range(m, 0, -1):
        for i in range(n):
            gi, yi = g[i], ymx[i]
            for q in range(i, lim[i] + 1):
                need_g = yi[q] == k          # 这一对的 ymx 正好是 k,用第 k+1 层补齐 g
                if need_g:
                    gi[q] = prev[i][q] + 1
        cur: Grid = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            row, gi = cur[i], g[i]
            if rank[i] < k:                  # 第 i 列没有待覆盖的点:整列跳过
                nxt = cur[i + 1]
                for j in range(i, n):
                    row[j] = nxt[j]
                continue
            for j in range(i, n):
                best = INF
                for q in range(i, min(lim[i], j) + 1):
                    v = gi[q] + cur[q + 1][j]  # q+1 > j 时后一项是 0(空区间)
                    if v < best:
                        best = v
                row[j] = best
        prev = cur
    return prev[0][n - 1]                    # 第 1 层覆盖全部列


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    T = next(data)
    out: list[int] = []
    for _ in range(T):
        n, S = next(data), next(data)
        points = [(next(data), next(data)) for _ in range(n)]
        xs, rank, hval = compress(points)
        out.append(min_rects(xs, rank, hval, S))
    print('\n'.join(map(str, out)))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

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-08 01:09
 * update_at: 2026-10-08 01:09
 */

// ROJ 1769《景中人》
// 平面上 n 个点,用最少的矩形覆盖所有点:矩形形如 [a,b] x [0,h](底边贴在 y=0),
// 面积 (b-a)*h <= S。多组数据。
//
// 做法(区间 DP,按高度分层):
//   1. 同一横坐标只需保留最高的那个点(矩形覆盖 (x,y) 当且仅当 x 落在底边区间内且 y <= h)。
//      于是压缩成 nn 列:第 t 列的横坐标 colX[t]、最高点的高度排名 colY[t](1 最小,m 最大)。
//   2. 关键性质:存在一组最优解,任意两个矩形的底边区间"相离或包含"。
//      证明:两区间相交但不包含时(a1 < a2 <= b1 < b2),设两矩形高度 h1、h2。
//      若 h1 >= h2,把矩形 2 截短成 [b1,b2]:它原来在 [a2,b1] 里盖住的点都满足 y <= h2 <= h1
//      且横坐标落在 [a1,b1] 内,已被矩形 1 覆盖;反之 h1 < h2 时把矩形 1 截短成 [a1,a2],
//      它原来在 [a2,b1] 里盖住的点都满足 y <= h1 < h2 且横坐标落在 [a2,b2] 内,被矩形 2 覆盖。
//      两种情形都不增加矩形数,反复操作即得"相离或包含"的解。
//   3. 层叠结构下按"最左列"分解:设 dp[k][i][j] 表示覆盖列 i..j 中高度排名 >= k 的点
//      所需的最少矩形数。取最左的待覆盖列 i,覆盖它最高点的那个"最外层"矩形
//      (它不可能被别的矩形包含)底边必是 [colX[i], colX[q]],q 越大宽度越大、允许高度越低,
//      所以高度取允许的最大值 ymx[i][q] = max{h : h*(colX[q]-colX[i]) <= S}。
//      该矩形把列 i..q 中高度 <= ymx 的点全部覆盖,剩余的点只能是列 i..q 中高度 > ymx 的点
//      (由嵌在它内部的矩形处理)和列 q+1..j 的点(与它相离):
//          dp[k][i][j] = min_{q} ( g[i][q] + dp[k][q+1][j] ),   g[i][q] = 1 + dp[ymx+1][i][q]
//      其中 q 必须满足 ymx[i][q] >= colY[i](否则矩形盖不住第 i 列最高点,它就不该是最外层),
//      这类 q 构成前缀 [i, limQ[i]];又因为 xs[q]-xs[i] <= xs[j]-xs[i] 时 g[i][q] 不会更优,
//      只需 q <= j。colY[i] < k(第 i 列没有待覆盖的点)时 dp[k][i][j] = dp[k][i+1][j]。
//   4. k 从 m 降到 1 逐层计算(转移里 ymx+1 > k,上一层已算好),同层内区间长度递增。
//      答案 = dp[1][1][nn]。
// 复杂度:区间状态 O(nn^2 * m) 个,每个转移 O(nn),总 O(nn^3 * m);
//        nn,m <= 100、T <= 10,实测最坏测试点 < 0.5 s。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 105;      // 题面上限 n <= 100,留少量安全余量
const int INF = 1000000000;

struct Point {
    int x;
    int y;
};
Point pt[MAXN];            // 输入的点(先按 x 升序、x 相同时按 y 降序排好)

bool cmpPoint(Point a, Point b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y > b.y;
}

ll S;                      // 单个矩形的面积上限
int colX[MAXN];            // 压缩后第 t 列的横坐标(1-based)
int colY[MAXN];            // 第 t 列最高点的高度排名(1-based,越大越高)
int hVal[MAXN];            // 高度排名 -> 实际高度
int ymxTab[MAXN][MAXN];    // ymxTab[i][q]:底边横跨列 i..q 时允许的最大高度排名
int limQ[MAXN];            // limQ[i]:仍能盖住第 i 列最高点的最大 q(q 再大允许高度就不够)
int g[MAXN][MAXN];         // g[i][q] = 1 + dp[ymx+1][i][q]:一条横跨 i..q 的矩形 + 它内部剩余
int dp[MAXN][MAXN][MAXN];  // dp[k][i][j]:覆盖列 i..j 中高度排名 >= k 的点所需最少矩形数

void solve() {
    int T;
    if (scanf("%d", &T) != 1) return;
    while (T--) {
        int n;
        if (scanf("%d %lld", &n, &S) != 2) return;
        for (int i = 1; i <= n; i++) scanf("%d %d", &pt[i].x, &pt[i].y);
        if (n <= 0) {
            printf("0\n");
            continue;
        }

        sort(pt + 1, pt + n + 1, cmpPoint);

        // 多组数据必须清空记忆化数组:上一组的 nn / m 可能更大,残留值会污染这一组
        memset(dp, 0, sizeof(dp));
        memset(g, 0, sizeof(g));

        // 列压缩:同一横坐标只保留最高点;再对高度排名离散化
        int nn = 0;
        int rawY[MAXN];                    // 每列最高点的实际高度
        for (int i = 1; i <= n; i++) {
            if (i == 1 || pt[i].x != pt[i - 1].x) {
                nn++;
                colX[nn] = pt[i].x;
                rawY[nn] = pt[i].y;        // 同 x 已按 y 降序,第一条就是最高点
            }
        }
        int m = 0;
        for (int i = 1; i <= nn; i++) hVal[i] = rawY[i];
        sort(hVal + 1, hVal + nn + 1);
        for (int i = 1; i <= nn; i++)
            if (i == 1 || hVal[i] != hVal[m]) hVal[++m] = hVal[i];
        for (int i = 1; i <= nn; i++)
            colY[i] = lower_bound(hVal + 1, hVal + m + 1, rawY[i]) - hVal;

        // ymxTab 随宽度单调不增,用双指针一次扫完;宽度 0 时高度不受限制,取最高档 m
        for (int i = 1; i <= nn; i++) {
            ymxTab[i][i] = m;
            int h = m;
            for (int q = i + 1; q <= nn; q++) {
                ll width = (ll)colX[q] - colX[i];
                while (h > 0 && (ll)hVal[h] * width > S) h--;   // 宽度变大,允许高度只降不升
                ymxTab[i][q] = h;
            }
        }
        for (int i = 1; i <= nn; i++) {
            limQ[i] = i;
            for (int q = i + 1; q <= nn; q++) {
                if (ymxTab[i][q] < colY[i]) break;
                limQ[i] = q;
            }
        }

        // dp[m+1][*][*] 保持全 0(全局数组初值):高度排名超过 m 就没有点需要覆盖
        for (int k = m; k >= 1; k--) {
            // 补齐 ymx == k 的 g:它用到 dp[k+1],此刻已算好
            for (int i = 1; i <= nn; i++)
                for (int q = i; q <= limQ[i]; q++)
                    if (ymxTab[i][q] == k) g[i][q] = dp[k + 1][i][q] + 1;
            for (int i = nn; i >= 1; i--) {
                if (colY[i] < k) {
                    // 第 i 列没有待覆盖的点:整列跳过
                    for (int j = i; j <= nn; j++) dp[k][i][j] = dp[k][i + 1][j];
                    continue;
                }
                for (int j = i; j <= nn; j++) {
                    int best = INF;
                    int qm = limQ[i] < j ? limQ[i] : j;
                    for (int q = i; q <= qm; q++) {
                        int v = g[i][q] + dp[k][q + 1][j];   // q+1 > j 时后一项为 0
                        if (v < best) best = v;
                    }
                    dp[k][i][j] = best;
                }
            }
        }
        printf("%d\n", dp[1][1][nn]);
    }
}

int main() {
    solve();
    return 0;
}

复杂度

  • 时间:状态数是 O(nn2m)O(nn^2 m),每个状态的转移枚举 qq,最坏 O(nn)O(nn),故最坏 O(nn3m)O(nn^3 m); 实际上 limQ⁡i\operatorname{limQ}_i 往往远小于 nnnn(底边一宽,允许高度就掉得很快),真实数据的计算量比上界小很多。 nn,m⩽100nn, m \leqslant 100、T⩽10T \leqslant 10,C++ 版在含 T=10T=10 组 nn=m=100nn=m=100 的最重测试点上实测约 0.010.01 s(限时 1000 ms); 构造的最坏形态(100 列紧挨、高度 1…1001 \dots 100 互不相同、S=2×105S = 2 \times 10^5)也只有 0.0110.011 s。
  • 空间:C++ 版开 dp[k][i][j]dp[k][i][j] 三维数组,O(nn2m)O(nn^2 m),约 4.64.6 MB; Python 版只滚动保留第 k+1k+1 层与第 kk 层,O(nn2)O(nn^2)。都远低于 256 MB。
  • 与 C++ 解法的关系:两份代码是同一个算法,Python 版把三维数组压成滚动两层, 转移顺序、剪枝完全一致。Python 版在同样的最重测试点上实测 0.170.17 s, 本题没有 Python 特有的 TLE 风险。

总结

  • 把几何直觉变成可用的结构性质:本题的难点不是"怎么枚举矩形",而是"最优解的矩形之间长什么样"。 「底边相离或包含」这一句话把二维覆盖问题压成了区间 DP,证明本身只有两行截短操作。
  • 贪心的直觉要验证:按最高点切左右是个非常顺手的错误想法,反例 (0,1),(50,100),(100,1),S=100(0,1),(50,100),(100,1), S=100 说明矮而宽的矩形能横跨子问题。做题时凡是"切成两个独立子问题"的推导,都值得问一句 “有没有东西能横跨这条切线”。
  • 宽高互换是本题的剪枝来源:ymx⁡(i,q)\operatorname{ymx}(i,q) 随 qq 单调不增,于是"盖得住第 ii 列最高点" 的合法 qq 是一个前缀,qq 的上界 limQ⁡i\operatorname{limQ}_i 一次扫完即可。
  • 多组数据必须清空记忆化数组:dpdp 的第三维上界由本组的 mm 决定,上一组 mm 更大时残留值会被这一组 当成 dp[m+1][⋅][⋅]=0dp[m+1][\cdot][\cdot] = 0 读走。写这份代码时正是靠"单组手算样例正确、整文件出错"的差异定位到这个坑; 多组数据题一律在每组开头把 DP 数组清干净。
  • 关于本题数据:素材源里带 data.py 生成脚本,data/ 是自造数据(.out 由素材 std.cpp 跑出), 题面也是网络重建,因此这 10 个测试点只覆盖了这份标准程序的算法行为,不等价于官方原题数据。 素材 std.cpp 用的是同一区间 DP 的另一种写法(枚举"分裂点"与"整跨矩形"), 本地实测它在 10 个测试点上与本解法的输出完全一致;本解法的正确性另外用精确暴力 (枚举所有有用矩形做集合覆盖)在 n⩽8n \leqslant 8 的随机数据上对拍过。