题目
题解
先将横坐标离散化，下文提到的横坐标都是离散化后的值。
接着考虑dp
设\(dp_{i, j}\)表示横坐标为\(i\)到\(j\)区间内的答案。
于是有两种转移- 找一个横坐标， 使得没有任意一个矩形穿过它， 枚举转移即可。
- 找一个不到横坐标，使得没有任意一个矩形， 那么直接选横坐标范围为[i,j]的矩形，于是把这个矩形的高度设到最高即可\((\)以我的语文水平可能描述的不是很清楚， 具体看代码\()\)。
代码
#include#include #include #include #include using namespace std;const int INF = 0x7F7F7F7F;const int N = 110;int x[N], y[N];int maxy[N];int num[N], total;int f[N][N], d[N];int main(){ int T; scanf("%d", &T); while (T--) { int n, s; scanf("%d %d", &n, &s); for (int i = 1; i <= n; i++) scanf("%d %d", &x[i], &y[i]); total = 0; for (int i = 1; i <= n; i++) num[++total] = x[i]; sort(num + 1, num + 1 + total); total = unique(num + 1, num + 1 + total) - num - 1; for (int i = 1; i <= n; i++) x[i] = lower_bound(num + 1, num + 1 + total, x[i]) - num; memset(maxy, 0, sizeof(int) * (total + 1)); for (int i = 1; i <= n; i++) maxy[x[i]] = max(maxy[x[i]], y[i]); for (int i = 1; i <= total; i++) for (int j = 1; j + i - 1 <= total; j++) { f[j][j + i - 1] = INF; int maxh = 0; for (int k = j; k <= i + j - 1; k++) maxh = max(maxh, maxy[k]); for (int k = j; k < i + j - 1; k++) f[j][j + i - 1] = min(f[j][j + i - 1], f[j][k] + f[k + 1][j + i - 1]); if ((num[j + i - 1] - num[j]) <= s / maxh) { f[j][j + i - 1] = 1; continue; } memset(d, 127, sizeof(d)); int lim = s / (num[j + i - 1] - num[j]); d[j - 1] = 0; for (int k = j; k <= j + i - 1; k++) { if (maxy[k] <= lim) d[k] = d[k - 1]; else for (int l = j; l <= k; l++) d[k] = min(d[k], f[l][k] + d[l - 1]); } f[j][j + i - 1] = min(f[j][j + i - 1], d[j + i - 1] + 1); } printf("%d\n", f[1][total]); } return 0;}