矩形底边都贴在 y=0,故存在「底边区间相离或包含」的最优解;按此性质对最左列做区间 DP,按高度分层转移,O(nn³m) 解决。
OJ: roj
题目 ID: 1769
难度:提高+/省选-
标签:动态规划区间DP贪心性质python
创建: 2026-10-08 01:09
更新: 2026-10-08 01:09
形式化题目
平面上有
- 一条边贴在直线
上,即矩形形如 ( , ); - 面积不超过
,即 。
点
求盖住全部点所需矩形数的最小值。多组数据:第一行
正解
思路
第一步:把"覆盖"翻译成两个方向的约束。
矩形
- 高度取定时,宽度上限是
; - 宽度取定时,高度上限是
。
这两句话是后面所有剪枝的来源:矩形越宽,允许的高度就越矮。
第二步:同一横坐标只留最高点。 由覆盖判据,矩形盖住
朴素做法与瓶颈。 一个自然的想法是枚举每个点属于哪个矩形,
一个诱人但错误的简化。 看到"矩形底边贴
按"最高点"分治:盖
第三步(关键性质):存在最优解,任意两个矩形的底边区间"相离或包含"。
任取两个底边区间相交但不包含的矩形,设为
- 若
:把矩形 2 截短成 。它原本盖住而新位置盖不到的点, 横坐标都在 内、高度不超过 ,已经落在矩形 1 里了。 - 若
:把矩形 1 截短成 。它原本盖住而新位置盖不到的点, 横坐标都在 内、高度不超过 ,已经落在矩形 2 里了。
两种情形都只把某个矩形变窄(面积更小、合法性不变)、矩形数不变,且不会让任何点失去覆盖。 每次操作后区间总长度严格减少,反复执行即可得到"两两相离或包含"的解,故该性质成立。
第四步:按"最左列"分解。 在这样一组解里,取覆盖最左待覆盖列
- 任何与
的底边区间相交的矩形,要么含于 、要么包含 ;后者与 的极大性矛盾, 所以它们全部含于 (这也说明 是最外层的)。 - 于是
的底边区间把问题切成互不相干的两块: 内部,和 右侧。
(宽度为
第五步:转移。 设
:第 列没有待覆盖的点,整列跳过, 。 - 否则第
列最高点必须被盖住,它就是上面那个 要负责的点,于是
其中
- 底边
必须盖得住第 列最高点,即 。 因为 随 单调不增(底边越宽、允许高度越矮),这类 正好是一个前缀, 右端点记作 ,扫一遍就能求出。 可以放心剪掉: 时矩形盖的列更多、允许的高度更低, 恒成立,留着也不会更优。
第六步:计算顺序。 转移里
用样例核对:
代码
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++ 版(同一算法):
/**
* 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;
}复杂度
- 时间:状态数是
,每个状态的转移枚举 ,最坏 ,故最坏 ; 实际上 往往远小于 (底边一宽,允许高度就掉得很快),真实数据的计算量比上界小很多。 、 ,C++ 版在含 组 的最重测试点上实测约 s(限时 1000 ms); 构造的最坏形态(100 列紧挨、高度 互不相同、 )也只有 s。 - 空间:C++ 版开
三维数组, ,约 MB; Python 版只滚动保留第 层与第 层, 。都远低于 256 MB。 - 与 C++ 解法的关系:两份代码是同一个算法,Python 版把三维数组压成滚动两层,
转移顺序、剪枝完全一致。Python 版在同样的最重测试点上实测
s, 本题没有 Python 特有的 TLE 风险。
总结
- 把几何直觉变成可用的结构性质:本题的难点不是"怎么枚举矩形",而是"最优解的矩形之间长什么样"。 「底边相离或包含」这一句话把二维覆盖问题压成了区间 DP,证明本身只有两行截短操作。
- 贪心的直觉要验证:按最高点切左右是个非常顺手的错误想法,反例
说明矮而宽的矩形能横跨子问题。做题时凡是"切成两个独立子问题"的推导,都值得问一句 “有没有东西能横跨这条切线”。 - 宽高互换是本题的剪枝来源:
随 单调不增,于是"盖得住第 列最高点" 的合法 是一个前缀, 的上界 一次扫完即可。 - 多组数据必须清空记忆化数组:
的第三维上界由本组的 决定,上一组 更大时残留值会被这一组 当成 读走。写这份代码时正是靠"单组手算样例正确、整文件出错"的差异定位到这个坑; 多组数据题一律在每组开头把 DP 数组清干净。 - 关于本题数据:素材源里带
data.py生成脚本,data/是自造数据(.out由素材std.cpp跑出), 题面也是网络重建,因此这 10 个测试点只覆盖了这份标准程序的算法行为,不等价于官方原题数据。 素材std.cpp用的是同一区间 DP 的另一种写法(枚举"分裂点"与"整跨矩形"), 本地实测它在 10 个测试点上与本解法的输出完全一致;本解法的正确性另外用精确暴力 (枚举所有有用矩形做集合覆盖)在的随机数据上对拍过。