P5975
XuYueming
·
·
题解
前言
题目链接：洛谷。
更好的体验？
好多错解都被我叉了，所以来贡献一发正确的题解，并予以解释。
题意简述
平面上有 n 个点，现在要求用最少的底边在 x 轴上且面积小于等于 S 的矩形覆盖所有点，这些矩形可以重叠。问最少矩形数量。矩形顶点不必是整点。
## 题目分析
~~没什么头绪。~~ 你想瞎搞贪心？那就在洛谷上愉快 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](https://www.luogu.com.cn/record/173053101)。
```cpp
// #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，再多记一维高度，然后套路地转移。