【BZOJ】P1766 photo

区间dp

理解了思路贼清晰。
先将点的x,y坐标离线。

状态定义

\(dp_{i,j,k}\)表示覆盖所有的点其x,y坐标满足\(x \in [i,j]\)且\(y \ge k\)所需的最小矩形数。

状态转移

两种方法:
1.\(dp_{i,j,k}\)由\(dp_{i,x,k}\)和\(dp_{x+1,j,k}\)转移过来（\(x\in[i,j-1]\)）。区间dp的标准转移形式，不谈。
2.尽可能的放一个最大的矩形。
方法：找到在\([i,j]\)中的最左端的点使得\(y\ge k\)以及最右端的点\(y\ge k\)的两点的x坐标，拿A除以两个的x坐标之差，这个值就是所放矩形的最大高度H。若\(H<k\)说明这个矩形覆盖不到当前所考虑的点，直接跳过，否则就进一步缩小范围，找\(y\)坐标大于\(H\)的左右两端点（设它们的x坐标为\(lx,rx\)），同时查询一波所有\(y\)坐标大于\(H\)的点中的\(y\)坐标的最小值\(h\),那么就有：

\[dp_{i,j,k}=min\{dp_{i,j,k},dp_{lx,rx,h}+1\}\]

代码:

#include<bits/stdc++.h>
using namespace std;
int n,A,B[10010],C[10010],m,sizeB,sizeD,dp[110][110][110],Max[10010],D[10010];
struct node {
????int x,y;
} P[10010];
bool cmp(node XX,node YY) {
????if(XX.x==YY.x)return XX.y<YY.y;
????else return XX.x<YY.x;
}
int main() {
????memset(dp,127,sizeof(dp));
????scanf("%d %d",&n,&A);
????for(int i=1; i<=n; i++)scanf("%d %d",&P[i].x,&P[i].y);
????for(int i=1; i<=n; i++)B[i]=P[i].y,D[i]=P[i].x;
????sort(B+1,B+1+n);
????sort(D+1,D+1+n);
????sizeB=unique(B+1,B+1+n)-B-1;
????sizeD=unique(D+1,D+1+n)-D-1;
????for(int i=1;i<=n;i++){
????????int pos=lower_bound(D+1,D+1+sizeD,P[i].x)-D;
????????Max[pos]=max(Max[pos],P[i].y);
????}
????for(int i=sizeD; i>=1; i--) {
????????for(int j=i; j<=sizeD; j++) {
????????????for(int k=sizeB; k>=1; k--) {
????????????????if(i==j){
????????????????????if(Max[i]>=B[k])dp[i][j][k]=1;
????????????????????else dp[i][j][k]=0;
????????????????????continue;
????????????????}
????????????????for(int o=i; o<=j-1; o++)dp[i][j][k]=min(dp[i][j][k],dp[i][o][k]+dp[o+1][j][k]);
????????????????int l,r;
????????????????for(l=i;l<=j;l++)if(Max[l]>=B[k])break;
????????????????for(r=j;r>=i;r--)if(Max[r]>=B[k])break;
????????????????if(l>r){
????????????????????dp[i][j][k]=0;
????????????????????continue;
????????????????}
????????????????else if(l==r){
????????????????????dp[i][j][k]=1;
????????????????????continue;
????????????????}
????????????????int y=A/(D[r]-D[l]),res=2e9+7;
????????????????if(y<B[k])continue;
????????????????for(l=i;l<=j;l++)if(Max[l]>y)break;
????????????????for(r=j;r>=i;r--)if(Max[r]>y)break;
????????????????for(int o=l;o<=r;o++)if(Max[o]>y)res=min(res,Max[o]);
????????????????if(res==2e9+7){
????????????????????dp[i][j][k]=min(dp[i][j][k],1);
????????????????????continue;
????????????????}
????????????????int num=lower_bound(B+1,B+1+sizeB,res)-B;
????????????????dp[i][j][k]=min(dp[i][j][k],dp[l][r][num]+1);
????????????}
????????}
????}
????cout<<dp[1][sizeD][1];
????return 0;
}

【BZOJ】P1766 photo

原文：https://www.cnblogs.com/SillyTieT/p/11220969.html