汕头市队赛 SRM10 dp只会看规律 && bzoj1766
2024-09-02 05:30:45
dp只会看规律 SRM 10
描述
平面上有n个点(xi,yi),用最少个数的底边在x轴上且面积为S的矩形覆盖这些点(在边界上也算覆盖)
输入格式
第一行两个整数n,S
接下来n行每行两个整数xi,yi,表示点的坐标
输出格式
一行,一个整数,表示答案
样例输入
6 4
5 1
4 1
7 1
6 4
5 4
2 1
样例输出
3
数据范围与约定
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=,inf=0x3f3f3f3f;
int read(){
int ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); 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=;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=;i<n;i++) e[i].y=lower_bound(yy,yy+m,e[i].y)-yy;
for(int r=;r<n;r++)
for(int l=r;l>=;l--){
int xd=e[r].x-e[l].x;
int hh=xd?upper_bound(yy,yy+m,S/xd)-yy:m;
for(int h=;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-;k>=;k--) mins(xl[k],xl[k+]),maxs(xr[k],xr[k+]);
for(int h=m-;h>=;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]+);
for(int k=l;k<r;k++) mins(F,f[l][k][h]+f[k+][r][h]);
}else if(xl[h]<=xr[h]) f[l][r][h]=f[xl[h]][xr[h]][h];
}
}
printf("%d\n",f[][n-][]);
return ;
}
最新文章
- opencv的学习笔记1
- Hibernate Projections(投影、统计、不重复结果)
- POJ 3041 Asteroids(最小点覆盖集)
- OkHttpUtils
- java中的IO流之文件复制
- sql中临时表的创建和使用【本文转自多人博客】
- dom4j处理java中xml还是很方便的
- maven 项目调试本地代码
- easyui表格自动换行
- 关于mysql中unique的插入Duplicate key
- centos7.2 环境下两个数据库的安装部署
- 无聊的js(马赛克)
- Tomcat配置SSL后使用HTTP后跳转到HTTPS
- HanLP中人名识别分析
- C# CountdownEvent实现
- 上传头像,layui上传图片
- Lamport Logical Clock 学习
- php $_SERVER中的一些选项说明
- Effective C++ 随笔(3)
- Git 基础 —— 常见使用场景