【STSRM10】dp只会看规律

【算法】区间DP

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

【题解】随机大数据下，贪心几乎没有错误，贪心出奇迹啊！

f[i][j][h]表示区间i~j高度>=h的点全部被覆盖的最少矩形。

首先离散化横纵坐标，然后初始化每个f[i][i]，然后进行区间DP(顺次枚举区间长度，左端点，高度从大到小）转移如下。

f[i][j][h]=min(f[i][j][h],f[i][x][h]+f[x+1][j][h])，x=i~j-1

h2=s/(x[j]-x[i])（注意离散化）

f[i][j][h]=min(f[i][j][h],f[i][j][h2+1]+1)

为什么这样转移是正确的？

考虑一个区间内情况，有以下两种选择：

1.分成两个区间各自摆矩形并列。

2.在整个区间设置打矩形，则h2部分另外处理。

其它情况？直接在区间摆大矩形覆盖全部等价于第二种情况，大区间h之上只有小区间的点等价于第一种情况，所以一共只有两种情况。

#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
int read()
{
    char c;int s=0,t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}while(isdigit(c=getchar()));
    return s*t;
}
/*------------------------------------------------------------*/
const int inf=0x3f3f3f3f,maxn=110;
struct cyc{int x,y;}a[maxn],b[maxn],c[maxn];
int n,f[maxn][maxn][maxn],ynum[maxn],tot,s;
bool cmp(cyc a,cyc b)
{return a.x<b.x||(a.x==b.x&&a.y>b.y);}
int main()
{
    scanf("%d%d",&n,&s);
    for(int i=1;i<=n;i++){
        a[i].x=read();
        a[i].y=read();
    }
    sort(a+1,a+n+1,cmp);
    int totx=1;
    c[totx]=a[1];
    for(int i=2;i<=n;i++)if(a[i].x!=a[i-1].x)c[++totx]=a[i];
    tot=n=totx;
    for(int i=1;i<=n;i++)a[i]=c[i];
    for(int i=1;i<=n;i++)ynum[i]=a[i].y;
    sort(ynum+1,ynum+tot+1);
    tot=unique(ynum+1,ynum+tot+1)-ynum-1;
    for(int i=1;i<=n;i++){b[i].x=i;b[i].y=lower_bound(ynum+1,ynum+tot+1,a[i].y)-ynum;}
    ynum[++tot]=inf;
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++){for(int k=tot;k>b[i].y;k--)f[i][i][k]=0;for(int k=b[i].y;k>=0;k--)f[i][i][k]=1;}
    for(int p=2;p<=n;p++){
        for(int i=1;i+p-1<=n;i++){
            int j=i+p-1;
            for(int h=tot;h>=0;h--){
                for(int x=i;x<j;x++)f[i][j][h]=min(f[i][j][h],f[i][x][h]+f[x+1][j][h]);
                int h2=lower_bound(ynum+1,ynum+tot+1,s/(a[j].x-a[i].x))-ynum;
                if(ynum[h2]==s/(a[j].x-a[i].x))h2++;
                f[i][j][h]=min(f[i][j][h],f[i][j][h2]+1);
            }
        }
    }
    printf("%d",f[1][n][0]);
    return 0;
}