P5975 photo 题解

laijinyi / 2024-09-23 / 原文

Solution

先离散化，记 $f(l,r,p)$ 为覆盖了 $[l,r]$ 区间内纵坐标 $\ge p$ 的点最少矩形个数。则：

\[ f(l,r,p)=\min(f(l,r,p),f(l,mid,p)+f(mid+1,r,p)) \]

\[ f(l,r,p)=\min(f(l,r,p),f(l,r,res)+1) \]

令 $h$ 为用面积为 $S$ 的矩形去覆盖 $[l,r]$ 区间的高度，即 $S/(r-l)$。其中 $res$ 为横坐标区间 $[l,r]$ 内纵坐标大于 $h$ 的最小高度。

Code

不保证输入输出格式正确。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
const int N = 110;
int n, S, Xtot, X[N], Ytot, Y[N], MxY[N], f[N][N][N];
vector<int> Ys[N];
struct Point {
	int x, y;
} a[N];

void init() {
	memset(f, 0, sizeof(f));
	memset(MxY, 0, sizeof(MxY));
	rep(i, 1, n) Ys[i].clear();
}

void solve() {
	cin >> n >> S, init(), Xtot = Ytot = 0;
	rep(i, 1, n) cin >> a[i].x >> a[i].y;
	sort(a + 1, a + n + 1, [&](Point u, Point v) {
		return u.x == v.x ? u.y < v.y : u.x < v.x;
	});
	rep(i, 1, n) X[++Xtot] = a[i].x, Y[++Ytot] = a[i].y;
	sort(X + 1, X + Xtot + 1), sort(Y + 1, Y + Ytot + 1);
	Xtot = unique(X + 1, X + Xtot + 1) - X - 1;
	Ytot = unique(Y + 1, Y + Ytot + 1) - Y - 1;
	auto GetX = [&](int x) { return lower_bound(X + 1, X + Xtot + 1, x) - X; };
	auto GetY = [&](int y) { return lower_bound(Y + 1, Y + Ytot + 1, y) - Y; };
	rep(i, 1, n) a[i].x = GetX(a[i].x), a[i].y = GetY(a[i].y);
	rep(i, 1, n) MxY[a[i].x] = max(MxY[a[i].x], a[i].y), Ys[a[i].x].push_back(a[i].y);
	rep(len, 1, Xtot) {
		rep(l, 1, Xtot - len + 1) {
			int r = l + len - 1;
			reo(p, Ytot, 1) {
				if (len == 1) {
					f[l][r][p] = p <= MxY[l];
				} else {
					f[l][r][p] = 2e9;
					rep(k, l, r - 1) f[l][r][p] = min(f[l][r][p], f[l][k][p] + f[k + 1][r][p]);
					int h = S / (X[r] - X[l]), res = Ytot + 1;
					rep(k, l, r) {
						int L = 0, R = Ys[k].size() - 1, mid = 0, Res = Ytot + 1;
						while (L <= R) {
							mid = (L + R) >> 1;
							if (Y[Ys[k][mid]] > h) Res = mid, R = mid - 1;
							else L = mid + 1;
						}
						if (Res != Ytot + 1) res = min(res, Ys[k][Res]);
					}
					f[l][r][p] = min(f[l][r][p], f[l][r][res] + 1);
				}
			}
		}
	}
	cout << f[1][Xtot][1] << '\n';
}

int main() {
	freopen("scene.in", "r", stdin), freopen("scene.out", "w", stdout);
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int t;
	cin >> t;
	while (t--) solve();
	return 0;
}