题目描述

　　平面上有\(n\)个点，你要用一些矩形覆盖这些点，要求：

• 每个矩形的下边界为\(y=0\)
• 每个矩形的大小不大于\(s\)

　　问你最少要用几个矩形。

　　\(n\leq 100,1\leq y\leq s\)

题解

　　先把坐标离散化。

　　猜（zheng）一个结论：最优解中任意两个矩形的横坐标只可能是相离或包含，不可能是相交。证明略。

　　考虑区间DP。

　　设\(f_{l,r,h}\)为覆盖横坐标\(l\sim r\)，纵坐标\(>h\)的所有矩形需要的最少次数。

　　枚举\(l,r,h\)，有两种转移：

• 找到一个横坐标\(i\)，使得没有任意一个矩形穿过\(i\)。枚举\(i\)分治即可。
• 放一个横坐标为\(l\sim r\)的矩形，把高度设为上限。

　　对于每一个\(h\)，这一层的转移是\(O(n^3)\)的，到下一层的转移是\(O(n^2\log n)\)的，所以总时间复杂度就是\(O(n^4)\)。

　　用记忆化搜索可以跑得飞快。

代码

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;typedef pair
        
          pii;int n,s;pii a[110];int f[110][110][110];int xx[110];int yy[110];int m1,m2;int d[110];int gao(int x){    return x?s/x:0x3fffffff;}int gao(int l,int r,int h){    int &s=f[h][l][r];    if(~s)        return s;    while(l<=r&&d[l]<=h)        l++;    while(l<=r&&d[r]<=h)        r--;    if(l>r)        return s=0;    int i;    s=0x7fffffff;    for(i=l;i