P2900 [USACO08MAR]土地购买Land Acquisition G

news/2024/10/30 17:25:57/

R e s u l t Result Result

...


H y p e r l i n k Hyperlink Hyperlink

https://www.luogu.com.cn/problem/P2900


D e s c r i p t i o n Description Description

n n n块土地,第 i i i块土地的长为 x i x_i xi,宽为 y i y_i yi ,现需将这些土地分成若干组,分成一组将产生这一组内长的最大值 × \times ×宽的最大值的代价,试确定一种分组方案,使得总代价最小

数据范围: n ≤ 5 × 1 0 4 , x i , y i ≤ 1 0 6 n\leq 5\times 10^4,x_i,y_i\leq 10^6 n5×104,xi,yi106


S o l u t i o n Solution Solution

将每个土地的长和宽抽象的看做是一个点 ( x , y ) (x,y) (x,y),注意到如果存在两个点 A ( x , y ) , B ( x ‘ , y ‘ ) A(x,y),B(x^`,y^`) A(x,y),B(x,y)满足 x ≤ x ‘ , y ≤ y ‘ x\leq x^`,y\leq y^` xx,yy,则 A A A这个点是可以舍弃的,因为显然当且仅当把它和 B B B划分到一起答案会更优。

如果我们把所有矩形按照 x x x为第一关键字升序排序,剩下来的点在第一象限中就构成了阶梯型。

f i f_i fi表示划分到第 i i i个矩形的最优代价
显然枚举 j j j表示把 [ j + 1 ∼ i ] [j+1\sim i] [j+1i]划分到一起得到方程 f i = m i n { f j + y j + 1 × x i } f_i=min\{f_j+y_{j+1}\times x_i\} fi=min{fj+yj+1×xi} x x x递增,所以最大值在 i i i取, y y y递减,所以最大值在 j + 1 j+1 j+1取】

可以证明或打表发现 f j f_j fj后面那坨满足四边形不等式,即 f f f具有决策单调性

如此,我们只需考虑每个决策对后续转移的影响,然后二分出决策的赚一点即可

时间复杂度: O ( n log ⁡ 2 n ) O(n\log_2 n) O(nlog2n)


C o d e Code Code

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define LL long long
#define N 50010
using namespace std;int n,m,tl,hd,maxl;
struct node{LL x,y;}a[N];
struct note{int l,r,x;}que[N];
inline bool cmp(node x,node y){return x.x<y.x||x.x==y.x&&x.y>y.y;}
LL f[N];
inline LL read()
{char c;LL d=1,f=0;while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;return d*f;
}
inline LL Cost(int i,int j){return f[i]+a[i+1].y*a[j].x;}
inline int findx(int i)
{int L=que[tl].l,R=que[tl].r,mid;while(L<=R){mid=L+R>>1;if(Cost(i,mid)<Cost(que[tl].x,mid)) R=mid-1;else L=mid+1;}return L;
}
signed main()
{n=read();for(register int i=1;i<=n;i++) a[i].x=read(),a[i].y=read();sort(a+1,a+1+n,cmp);for(register int i=1;i<=n;i++){while(m&&a[m].y<=a[i].y) m--;a[++m]=a[i];}que[hd=tl=1]=(note){1,m,0};for(register int i=1;i<=m;i++){while(hd<=tl&&que[hd].r<i) hd++;f[i]=Cost(que[hd].x,i);while(hd<=tl&&i<que[tl].l&&Cost(i,que[tl].l)<Cost(que[tl].x,que[tl].l)) tl--;int u=findx(i);que[tl].r=u-1;if(u<=m) que[++tl]=(note){u,m,i};}printf("%lld",f[m]);
}

http://www.ppmy.cn/news/203947.html

相关文章

ccpd文件名转成xml_Fedora 16 64bit 下安装 LBP2900打印机

Fedora 16 64bit下安装 LBP2900打印机 Hello. Im goingo to post the new guide for the installation of Canon LBP2900 series on Fedora 17. I think that this guide may be useful for all Canon LBP series. 1)open root terminal and dont connect the printer 2) insta…

电脑加内存遇到的不开机问题解决

电脑系统是win7 电脑是联想台式机 简单配置如下 自己找了个神州电脑的4G内存条想加上升级一下&#xff0c;当天直接关机然后没有断电源&#xff0c;直接把内存条搞上去&#xff0c;然后重启&#xff0c;系统没问题显示是8G内存。 结果第二天来了就坑爹了&#xff0c;发现系…

oracle_j000,DBA手记:System State转储之ROW CACHE对象

DBA手记:System State转储之ROW CACHE对象 在《Oracle DBA手记 3》即将出版之际&#xff0c;我将《Oracle DBA手记 2》上收录的一些文章发布出来&#xff0c;与大家分享。前文参考&#xff1a; http://www.eygle.com/archives/2011/05/dbasystem_state_file.html 1.1ROW CACHE对…

bzoj2900

2900: 好玩的数字游戏 Time Limit: 10 Sec Memory Limit: 512 MB Submit: 7 Solved: 4 [ Submit][ Status][ Discuss] Description TK在虐题的同时&#xff0c;也喜欢玩游戏。 现在&#xff0c;有这样的一个游戏&#xff0c;规则是这样的&#xff1a; 先随机给出一个数字N&am…

打印服务器 支持 佳能 2900+打印机,佳能LBP2900,夏普等特殊打印机如何实现打印?(虚拟USB软件用途之二)...

原理解释 一些特殊语言的打印机比如佳能的LBP系列(CAPT语言)理光的部分型号(DDST语言),是不支持Windows自带的TCP/IP协议共享打印,为了实现多台电脑共享打印机就需要用到这个虚拟USB自动连接工具,工具在运行时,会检测打印机的任务列表有无需要打印的任务,有任务时软件自动…

C/C++动态内存管理 ,new和delete

目录 C动态内存管理 内置类型的动态内存管理 自定义类型的动态内存管理 new和delete的实现原理 new和malloc、delete和free的异同 new的其他用法&#xff1a;定位new C语言动态内存管理<-点这里 C动态内存管理 因为C语言中的管理方式使用起来不方便而且有些情况下无…

基于JSP+SQL的机房自由上机收费管理软件的设计与实现

为了提高机房管理者的管理效率和减轻管理者的劳动强度,提高机房的利用率,发挥计算机的方便性和快捷性,提出了机房自由上机收费管理系统的设计方案。 机房自由上机收费系统是典型的数据库管理系统,其开发主要包括后台数据库的建立和维护以及前端应用程序的开发两个方面,对于…

快速掌握 LightGBM 必备知识点,十问十答

文章目录 1. 什么是LightGBM&#xff1f;2. LightGBM与XGBoost的区别是什么&#xff1f;3. 如何安装LightGBM&#xff1f;技术交流4. 如何使用LightGBM进行模型训练&#xff1f;5. 如何使用LightGBM进行模型预测&#xff1f;6. LightGBM如何处理缺失值&#xff1f;7. LightGBM中…