汕头市队赛 SRM10 dp只会看规律 && bzoj1766

dp只会看规律 SRM 10

描述

平面上有n个点(xi,yi)，用最少个数的底边在x轴上且面积为S的矩形覆盖这些点（在边界上也算覆盖）

输入格式

第一行两个整数n,S
接下来n行每行两个整数xi,yi,表示点的坐标

输出格式

一行，一个整数，表示答案

样例输入

样例输出

数据范围与约定

n=3，1组数据
n=5，1组数据
n=11，1组数据
n=15，1组数据
n=18，1组数据
18<n<=100，7组数据
对于所有的数据，
1<=n<=100
0<=xi<=3000000
1<=yi<=S
1<=S<=200000

样例解释

这里给出一种方案，每行为一个矩形：
1<=x<=3,0<=y<=2
3<=x<=7,0<=y<=1
5<=x<=6,0<=y<=4

————————————————————————————

这道题状压dp有四十分QAQ orzzsn

正解是一波dp

通过画图可知两个矩形之间的关系除了互不相交就是互相包含

并且互相包含的情况中间的高度必须大于x长度比他大的

这样我们就可以枚举左右区间以及高度（高度从大到小）

当然我们要先给 x y 离散化降低一波复杂度这个时候的复杂度才能做到n^4

当然如果一个 l r 的组合中他的左右边界上不存在点我们可以强行挪到点上这可以作为一波剪枝

dp的时候注意h比较小的区间 l r 要包含或者等于h比他大的区间这样才能保证正确性

这样我们可以每一层类似递归的处理下去判断一下两种情况就可以做辣

f【l】【r】【h】表示左右端点为 l r 高度为 h 的区间覆盖所有点的最小答案

xd表示当前 l r 的区间长度 hh是区间的最大高度

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=157,inf=0x3f3f3f3f;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
struct node{int x,y;}e[M];
bool cmp(node a,node b){return a.x<b.x;}
int yy[M],xl[M],xr[M],n,m,S,f[M][M][M];
void maxs(int& x,int y){if(x<y) x=y;}
void mins(int& x,int y){if(x>y) x=y;}
int main()
{
    n=read(); S=read();
    for(int i=0;i<n;i++) e[i].x=read(),e[i].y=read(),yy[i]=e[i].y;
    sort(e,e+n,cmp);
    sort(yy,yy+n);
    m=unique(yy,yy+n)-yy;
    for(int i=0;i<n;i++) e[i].y=lower_bound(yy,yy+m,e[i].y)-yy;
    for(int r=0;r<n;r++)
        for(int l=r;l>=0;l--){
            int xd=e[r].x-e[l].x;
            int hh=xd?upper_bound(yy,yy+m,S/xd)-yy:m;
            for(int h=0;h<m;h++) xl[h]=inf,xr[h]=-inf;
            for(int k=l;k<=r;k++) mins(xl[e[k].y],k),maxs(xr[e[k].y],k);
            for(int k=m-2;k>=0;k--) mins(xl[k],xl[k+1]),maxs(xr[k],xr[k+1]);
            for(int h=m-1;h>=0;h--){
                if(xl[h]==l&&xr[h]==r){
                    int& F=f[l][r][h];
                    F=inf;
                    if(h<hh) mins(F,f[l][r][hh]+1);
                    for(int k=l;k<r;k++) mins(F,f[l][k][h]+f[k+1][r][h]);
                }else if(xl[h]<=xr[h]) f[l][r][h]=f[xl[h]][xr[h]][h];
            }
        }
    printf("%d
",f[0][n-1][0]);
    return 0;
}

View Code