题目链接。
可过掉帖子中的所有 Hack 数据。
Analysis
\(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\) 为用面积为 \(A\) 的矩形去覆盖 \([l,r]\) 区间的高度，即 \(A / (r-l)\)。
其中 \(res\) 为横坐标区间 \([l,r]\) 内纵坐标大于 \(h\) 的最小高度。
具体细节见代码。
CODE
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n,A,x[N],y[N],a[N],b[N],L,f[N][N][N];
int mx[N];
int main(){
scanf("%d%d",&n,&A);
for(int i=1;i<=n;++i){
scanf("%d%d",&x[i],&y[i]);
a[i] = x[i], b[i] = y[i];
}
// 离散化
sort(a+1,a+n+1), sort(b+1,b+n+1);
int cnta = unique(a+1,a+n+1)-a-1;
int cntb = unique(b+1,b+n+1)-b-1;
for(int i = 1;i<=n;++i){
x[i] = lower_bound(a+1,a+cnta+1,x[i])-a;
y[i] = lower_bound(b+1,b+cntb+1,y[i])-b;
mx[x[i]] = max(mx[x[i]],y[i]);
}
n = cnta;
// f[l][r][p] 表示覆盖了 [l,r] 区间内 纵坐标 >=p 的点最矩形个数
for(int len = 1;len<=n;++len){
for(int l = 1,r = len;r<=n;++l,++r){
for(int p = cntb;p;--p){
f[l][r][p] = n;
int L = l, R = r;
while(L <= n && mx[L] < p)++L;
while(R && mx[R] < p)--R;
// 找到中间 最大值大于 p 的 [L,R] 区间
if(L > R){ f[l][r][p] = 0; continue; }
if(L == R){ f[l][r][p] = 1; continue; }
if(l != L || r != R){ f[l][r][p] = f[L][R][p]; continue; }// 可直接继承
for(int mi = L;mi < R;++mi)f[l][r][p] = min(f[l][r][p],f[l][mi][p]+f[mi+1][r][p]);
// 直接拼起来
int h = A / (a[R] - a[L]); int res = 101;
// h 为覆盖 L~R 的最大高度
for(int j = L;j<=R;++j)if(b[mx[j]] > h)res = min(res,mx[j]);
// res 统计大于 h 的最小纵坐标
if(res > p)f[l][r][p] = min(f[l][r][p],f[l][r][res] + 1);
}
}
}
printf("%d\n",f[1][n][1]);
return 0;
}