#斜率优化#JZOJ 2204 洛谷 2900 BZOJ 1597 土地购买

news/2024/4/19 16:43:07/

题目


分析

首先把宽度 l l l按第一关键字从小到大排序,高度 h h h按第二关键字从大到小排序,用一个栈把存在 h [ x ] ≤ h [ y ] , l [ x ] ≤ l [ y ] h[x]\leq h[y],l[x]\leq l[y] h[x]h[y],l[x]l[y]的情况消掉,然后一个显然的性质可以发现最优情况肯定是选择连续的一段,那么可以这样列出dp方程
d p [ i ] = min ⁡ { d p [ j ] + h [ j + 1 ] ∗ l [ i ] } dp[i]=\min\{dp[j]+h[j+1]*l[i]\} dp[i]=min{dp[j]+h[j+1]l[i]}
k ( j &lt; k ) k(j&lt;k) k(j<k)优于 j j j,那么 d p [ j ] + h [ j + 1 ] ∗ l [ i ] ≥ d p [ k ] + h [ k + 1 ] ∗ l [ i ] dp[j]+h[j+1]*l[i]\geq dp[k]+h[k+1]*l[i] dp[j]+h[j+1]l[i]dp[k]+h[k+1]l[i]
那么化简可得 d p [ j ] − d p [ k ] ≥ ( h [ k + 1 ] − h [ j + 1 ] ) ∗ l [ i ] dp[j]-dp[k]\geq (h[k+1]-h[j+1])*l[i] dp[j]dp[k](h[k+1]h[j+1])l[i]
因为若 h [ k + 1 ] ≥ h [ j + 1 ] h[k+1]\geq h[j+1] h[k+1]h[j+1],那么 l [ k + 1 ] &gt; l [ j + 1 ] l[k+1]&gt;l[j+1] l[k+1]>l[j+1]也不符合消掉的情况,所以 h [ k + 1 ] &lt; h [ j + 1 ] h[k+1]&lt;h[j+1] h[k+1]<h[j+1]
d p [ j ] − d p [ k ] h [ k + 1 ] − h [ j + 1 ] ≤ l [ i ] \frac{dp[j]-dp[k]}{h[k+1]-h[j+1]}\leq l[i] h[k+1]h[j+1]dp[j]dp[k]l[i]
显然 l l l是单调递增的,所以维护下凸壳,单调队列优化,时间复杂度 O ( n ) O(n) O(n)


代码

#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
struct rec{int x,y;bool operator <(const rec &t)const{return x<t.x||(x==t.x&&y>t.y);}
}a[50001];
long long dp[50001]; int n,top,head,tail,q[50001];
inline signed iut(){rr int ans=0; rr char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans;
}
inline double slope(int j,int k){return 1.0*(dp[k]-dp[j])/(a[j+1].y-a[k+1].y);}
signed main(){n=iut();for (rr int i=1;i<=n;++i) a[i]=(rec){iut(),iut()};sort(a+1,a+1+n);for (rr int i=1;i<=n;++i){while (top&&a[top].y<=a[i].y) --top;a[++top]=a[i];}n=top,head=1,tail=0,q[++tail]=0;for (rr int i=1;i<=n;++i){while (head<tail&&slope(q[head],q[head+1])<=a[i].x) ++head;dp[i]=dp[q[head]]+1ll*a[i].x*a[q[head]+1].y;while (head<tail&&slope(q[tail-1],q[tail])>=slope(q[tail],i)) --tail;q[++tail]=i;}return !printf("%lld",dp[n]);
} 

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

相关文章

JavaScript实例(Visual Studio Code)(一)

JavaScript程序本身不能独立存在 它是依附于某个HTML页面 在浏览器端运行的 基本语法&#xff1a; <script type"text/javascript" [src"外部js文件"]>... </script> 语法说明&#xff1a; script为脚本标记&#xff0c;它必须以<scri…

BZOJ2900 好玩的数字游戏

好玩的数字游戏 TK在虐题的同时&#xff0c;也喜欢玩游戏。现在&#xff0c;有这样的一个游戏&#xff0c;规则是这样的&#xff1a;先随机给出一个数字N&#xff0c;然后你在操场上把1到N的所有数字写成一排&#xff0c;就像这样&#xff1a;123456789101112131415….接着你在…

web day16(log4j日志框架、事务)

1.log4j概述 log4j log for java专门为Java提供的日志框架 是目前公司中Java语言收集日志的主流日志框架 a.特点&#xff1a; 收集的优先级 收集数据的目的地 文件 console 收集数据的展示形式 HTML pattern 2.如何使用log4j a.在程序中导入log4j 的jar包 b.书写配置文件 log4j…

P2900 [USACO08MAR]土地购买Land Acquisition G

文章目录 R e s u l t Result Result H y p e r l i n k Hyperlink Hyperlink D e s c r i p t i o n Description Description S o l u t i o n Solution Solution C o d e Code Code R e s u l t Result Result H y p e r l i n k Hyperlink Hyperlink https://www.luogu.co…

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中…

ClickHouse的join优化

概要&#xff1a; ClickHouse 最为擅长的领域是一个大宽表来进行查询&#xff0c;多表 JOIN 时Clickhouse 性能表现不佳。 CK执行模式 第一阶段&#xff0c;Coordinator 收到查询后将请求发送给对应的 worker 节点&#xff1b;第二阶段&#xff0c;Coordinator 收到各个 work…

计算机视觉实习生面经(百度 | 地平线 | 小米 | 旷视 | 快手)

计算机视觉实习生面经 1. 百度&#xff08;计算机视觉实习生&#xff0c;ACG&#xff0c;自动驾驶&#xff09;——2021/05一面二面 2. 地平线&#xff08;感知算法实习生&#xff0c;北京&#xff09;——2021/083. 小米&#xff08;计算机视觉实习生&#xff0c;AI Lab&#…

Linux题库100道

cron 后台常驻程序 (daemon) 用于&#xff1a;(D) A. 负责文件在网络中的共享B. 管理打印子系统C. 跟踪管理系统信息和错误D. 管理系统日常任务的调度在大多数Linux发行版本中&#xff0c;以下哪个属于块设备 (block devices) &#xff1f;(B) A. 串行口B. 硬盘C. 虚拟终端D.…

学计算机专业选啥价位的笔记本,大学生买笔记本电脑要怎么选?这些电脑值得考虑,千万别选错了!...

办公笔记本。 办公与游戏 对于办公游戏都有要求的朋友来说&#xff0c;这样的电脑就得要CPU、显卡、内存、硬盘都要充分考虑&#xff0c;CPU要高&#xff0c;显卡也要高&#xff0c;内存也要高&#xff0c;硬盘容量也要大&#xff0c;它的价格通常都是在6000以上&#xff0c;推…

r720支持多少频率的内存吗_高频内存对游戏帧数影响大吗?2400MHz和3200MHz频率内存对比实测...

内存频率对电脑性能无疑是有一定的影响&#xff0c;但是在日常使用根本也发现不了明显变化。我们知道&#xff0c;目前DDR4主流内存频率通常是2400MHz或者2666MHz&#xff0c;在主板支持更高内存频率的情况下&#xff0c;如果搭配高频内存是否对游戏帧数有所提升&#xff1f;该…

学习神经网络(深度学习)电脑的配置要求

学习神经网络&#xff08;深度学习&#xff09;电脑的配置要求 个人电脑配置与使用感受&#xff08;电脑小白&#xff09; 我目前所使用的电脑的配置是 &#xff08;1&#xff09;CPU&#xff1a;i5-9300H &#xff08;2&#xff09;显卡&#xff08;GPU&#xff09;&#xf…

3d图形设计计算机配置,3d建模电脑配置要求高吗?这样配电脑不多花一分钱

3d建模电脑配置要求高吗?做3d建模笔记本配置价位大概要花多少呢?本期&#xff0c;模型云就为你您整理了这些3d建模电脑配置详细清单&#xff0c;跟着我们来一起看看这些适合做3d建模的电脑配置吧! 3d建模电脑配置要求高吗? 影响3d建模电脑配置要求的主要还是看你使用的建模软…

对于一个程序员来说,电脑的内存需要多大?

1、 程序员电脑内存有多大内存够用足够了&#xff0c;纯写代码的编程对电脑要求不高&#xff0c;尤其对显卡几乎没有要求&#xff0c;一般编程可能开的任务窗口比较多&#xff0c;所以只要cpu和内存大点就可以了一般来说&#xff0c;处理器确实比显卡来得重要一些&#xff0c;因…