【题目描述】
有n个人在桥上。桥可以看成一个二维平面，那么每个人的位置都可以用一个坐标表示。
Yazid想用矩形把他们都覆盖住。他规定单个矩形的面积不能超过S，并且矩形的一条边必须贴着下栏杆（直线y=0）。
请你告诉他，他至少要用几个矩形才能覆盖所有的景中人呢？
【输入】
本题包含多组数据。第一行一个整数T，表示数据组数。接下来依次描述各组数据，
对于每组数据：
第一行2个整数n,S，意义见问题描述。
接下来n行，每行2个非负整数x,y，描述一个人的横纵坐标。
【输出】
对于每组数据，一行一个整数表示所需要使用的最少的矩形数目。
【输入样例】
1
6 4
2 1
4 1
5 1
5 4
7 1
6 4
【输出样例】
3
【提示】
【数据规模】
对于10%的数据，保证n≤8，x≤10，S≤20。
对于30%的数据，保证n≤18，x≤700，S≤1024。
对于90%的数据，保证n≤90。
对于100%的数据，保证T≤10，n≤100，x≤3000000，1≤y≤S≤200000。
【题解】
发现每两个矩形相交而不包含的部分是没有意义的，所以最优的方法是任一两个矩形不是相离就是横坐标完全包含。
将每个点按横坐标排序，可以定义f[i][j][k]表示第i到j个点中覆盖了所有纵坐标小于等于k的点所花最小代价。可以使用记忆化搜索实现。
转移就是
①相离，f[i][j][k]=f[i][l][k]+f[l+1][j][k]。
②放一个横坐标覆盖整个区间的方块。f[i][j][k]=f[i‘][j‘][k‘]+1，i‘表示i右边第一个纵坐标大于k‘的点，j‘表示j左边第一个纵坐标大于k‘的点。k‘表示矩形的高度。
代码如下：
#include<bits/stdc++.h> using namespace std; const int N=105; int t,n,s,ls[N],tot,cnt,h[N],f[N][N][N]; struct people { int x,y; }a[N],b[N]; inline bool cmp(people x,people y) { if(x.x!=y.x) return x.x<y.x; return x.y>y.y; } inline int dp(int x,int xx,int gao) { if(f[x][xx][gao]>=0) return f[x][xx][gao]; bool pan=0; for(int i=x;i<=xx;i++) if(h[i]>=gao) pan=1; if(pan==0) return f[x][xx][gao]=0; if(x==xx) return f[x][xx][gao]=1; int zg=s/(double)(b[xx].x-b[x].x); int l=x,r=xx; while(l<=xx&&b[l].y<=zg) l++; while(r>=x&&b[r].y<=zg) r--; f[x][xx][gao]=100000; if(l>x||r<xx) { if(r<l) return f[x][xx][gao]=1; else { int gg=upper_bound(ls+1,ls+cnt+1,zg)-ls; f[x][xx][gao]=dp(l,r,gg)+1; } } for(int i=x;i<xx;i++) f[x][xx][gao]=min(f[x][xx][gao],dp(x,i,gao)+dp(i+1,xx,gao)); return f[x][xx][gao]; } int main() { cin>>t; while(t--) { cin>>n>>s; memset(f,-0x3f3f3f3f,sizeof(f)); for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y,ls[i]=a[i].y; sort(a+1,a+n+1,cmp); sort(ls+1,ls+n+1); cnt = unique(ls + 1,ls + n + 1)-(ls + 1); tot=0;a[0].x=-1; for(int i=1;i<=n;i++) if(a[i].x!=a[i-1].x) b[++tot]=a[i]; for(int i=1;i<=n;i++) h[i]=lower_bound(ls+1,ls+cnt+1,b[i].y)-ls; cout<<dp(1,tot,1)<<"\n"; } }
原文：https://www.cnblogs.com/betablewaloot/p/12198821.html
