自动搬运

查看原文

来自洛谷，原作者为

	XuYueming 没拿省一不改签

搬运于2025-08-24 22:16:08，当前版本为作者最后更新于2024-08-16 16:20:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言

题目链接：洛谷。

更好的体验？

好多错解都被我叉了，所以来贡献一发正确的题解，并予以解释。

题意简述

平面上有 $n$ 个点，现在要求用最少的底边在 $x$ 轴上且面积小于等于 $S$ 的矩形覆盖所有点，这些矩形可以重叠。问最少矩形数量。矩形顶点不必是整点。

$n \leq 100$。

题目分析

没什么头绪。 你想瞎搞贪心？那就在洛谷上愉快 A 掉这道题吧！（洛谷上管理还没加数据。）

先来找找性质。离散化是 naive 的，然后套路地，对于 $x$ 相同的点，只保留纵坐标最大的，这是显然的。假设我们放置了一个矩形 $x \in [l, r]$，那么一个显然不劣的贪心是让这个矩形的高度为 $\cfrac{S}{r-l}$，原因是能够包括更多的点。于是问题就变成了找出符合答案的若干区间，尝试用区间 DP 解决。

如果只记 $f_{l,r}$ 似乎并不好转移，故再记一维 $h$，用 $f_{l,r,h}$ 表示 $[l, r]$ 区间内不低于 / 不高于 $h$ 的点都被覆盖了。这两者似乎是等价的，但是后者是错误的，会在之后分析，这里使用前一种定义。

先来考虑边界情况。记 $h_i$ 表示 $x=i$ 时对应纵坐标。当 $x \in [l, r]$ 里，所有 $h_x$ 均比 $h$ 小时，$f_{l,r,h} = 0$；以及当只有一个点处在 $h$ 及上方，显然只用一个矩形就可以了。

考虑放置一个矩形。套路化地，我们只放置这个区间最左边的矩形，这样是能考虑到所有情况的。即，我们放置一个矩形 $x \in [l, o]$，计算出能覆盖哪些点，找出 $[l, o]$ 中不能被覆盖的最小纵坐标 $h'$，则 $f_{l,r,h}$ 可以从 $f_{l,o,h'} + f_{o + 1,r,h} + 1$ 转移而来。

当然，实现上的细节，比如当 $o=l$ 时可能会除以 $0$ 等不展开。

这么做的时间复杂度是 $\Theta(n^5)$，很容易发现在放置矩形的时候有重复计算，$\Theta(n^3)$ 预处理 $mi_{l,r}$ 表示放置一个矩形 $x \in [l, r]$，$l \sim r$ 里没被覆盖的最小纵坐标，可以做到 $\Theta(n^4)$ 的时间复杂度。当然，预处理可以是 $\Theta(n ^ 2 \log n)$，但是没必要。

当然可以继续优化…… 常数。比如，找到满足 $h_{l \sim L} < h$ 的最大 $L$，同理最小的 $R$，如果 $L \neq l \lor R \neq r$，那么 $f_{l,r,h}$ 和 $f_{L,R,h}$ 显然是等价的。边界所有 $h_x$ 均小于 $h$ 等价于 $L > R$，只有一个点等价于 $L = R$。把循环换成记忆化搜索能避免很多不必要的状态。

话说回来，为什么不能记不高于呢？我们很容易发现，如果放置了一个矩形，我们无法表示其上方剩余的点这种状态，所以是错误的。

时间复杂度：$\Theta(n ^ 4)$，空间复杂度：$\Theta(n ^ 3)$。

代码

正解里 rank1。

// #pragma GCC optimize(3)
// #pragma GCC optimize("Ofast", "inline", "-ffast-math")
// #pragma GCC target("avx", "sse2", "sse3", "sse4", "mmx")
#include <cstdio>
#include <algorithm>
using namespace std;

int n, S;
int x[110], y[110];
int rx[110], ry[110];
int cx, cy;
int hign[110];

int f[110][110][110];  // [l, r] >= h 都好了的
int mi[110][110];  // [l, r] 放置矩形，不能被覆盖到的最小纵坐标

bool visf[110][110][110];

int dfs(int l, int r, int h) {
    if (l > r || h > cy) return 0;
    if (visf[l][r][h]) return f[l][r][h];
    visf[l][r][h] = true, f[l][r][h] = n;
    int L = l, R = r;
    while (L <= R && hign[L] < h) ++L;
    while (R >= L && hign[R] < h) --R;
    if (L > R) return f[l][r][h] = 0;
    if (L == R) return f[l][r][h] = 1;
    if (L != l || R != r) return f[l][r][h] = dfs(L, R, h);
    for (int x = L; x <= R; ++x)
        f[l][r][h] = min(f[l][r][h], dfs(L, x, mi[L][x]) + dfs(x + 1, R, h) + 1);
    return f[l][r][h];
}

signed main() {
	scanf("%d%d", &n, &S);
	for (int i = 1; i <= n; ++i) {
		scanf("%d%d", &x[i], &y[i]);
		rx[i] = x[i], ry[i] = y[i];
	}
	sort(rx + 1, rx + 1 + n);
	sort(ry + 1, ry + 1 + n);
	cx = unique(rx + 1, rx + 1 + n) - rx - 1;
	cy = unique(ry + 1, ry + 1 + n) - ry - 1;
	for (int i = 1; i <= n; ++i) {
		x[i] = lower_bound(rx + 1, rx + 1 + cx, x[i]) - rx;
		y[i] = lower_bound(ry + 1, ry + 1 + cy, y[i]) - ry;
	}
	for (int i = 1; i <= n; ++i) {
		hign[x[i]] = max(hign[x[i]], y[i]);
	}
	n = cx;
	for (int l = 1; l <= n; ++l) {
		mi[l][l] = cy + 1;
		for (int r = l + 1; r <= n; ++r) {
			mi[l][r] = cy + 1;
			int mxh = S / (rx[r] - rx[l]);
			for (int i = l; i <= r; ++i)
				if (ry[hign[i]] > mxh)
					mi[l][r] = min(mi[l][r], hign[i]);
		}
	}
    printf("%d", dfs(1, n, 1));
	return 0;
}

后记

一道初看毫无头绪的题目，根据小贪心发现和区间有关，使用区间 DP，再多记一维高度，然后套路地转移。