2018.09.10 bzoj1597: [Usaco2008 Mar]土地购买(斜率优化dp)
2024-09-04 10:10:26
传送门
终究还是通宵了啊。。。
这是一道简单的斜率优化dp。
先对所有土地排序,显然如果有严格小于的两块土地不用考虑小的一块。
于是剩下的土地有一条边单增,另外一条单减。
我们假设a[i]是单减的,b[i]是单增的。
f[i]=min(f[j]+a[j+1]∗b[i])" role="presentation" style="position: relative;">f[i]=min(f[j]+a[j+1]∗b[i])f[i]=min(f[j]+a[j+1]∗b[i])
对于两个决策k1<k2" role="presentation" style="position: relative;">k1<k2k1<k2,如果k2优于k1,那么:
f[k1]−f[k2]>b[i]∗(a[k2+1]−a[k1+1])" role="presentation" style="position: relative;">f[k1]−f[k2]>b[i]∗(a[k2+1]−a[k1+1])f[k1]−f[k2]>b[i]∗(a[k2+1]−a[k1+1])
注意a是单减的除过去要变号。
<=>slope<b[i]" role="presentation" style="position: relative;">slope<b[i]slope<b[i]
于是可以斜率优化了。
代码:
#include<bits/stdc++.h>
#define N 50005
#define ll long long
using namespace std;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int n,tot=0,hd,tl,q[N];
ll f[N];
struct Node{ll a,b;}p_[N],p[N];
inline bool cmp(Node a,Node b){return a.a==b.a?a.b>b.b:a.a>b.a;}
inline double slope(int i,int j){return (f[i]-f[j])*1.0/(p[j+1].a-p[i+1].a);}
int main(){
n=read(),hd=tl=1;
for(int i=1;i<=n;++i)p_[i].a=read(),p_[i].b=read();
sort(p_+1,p_+n+1,cmp);
for(int i=1;i<=n;++i)if(tot==0||p_[i].b>p[tot].b)p[++tot]=p_[i];
for(int i=1;i<=tot;++i){
while(hd<tl&&slope(q[hd],q[hd+1])<p[i].b)++hd;
int j=q[hd];
f[i]=f[j]+p[i].b*p[j+1].a;
while(hd<tl&&slope(q[tl],i)<slope(q[tl-1],q[tl]))--tl;
q[++tl]=i;
}
cout<<f[tot];
return 0;
}
最新文章
- AJAX部分---php-jquery-ajax;
- docker中使用systemd
- Asp.Net生命周期系列六
- HTML5表单内元素的required属性
- 更改Zend Studio/Eclipse代码风格主题
- linux修改文本模式下的分辨率(CentOS6.4)
- [Swust OJ 188]--异面空间(读懂题意很重要)
- Java对象序列化/反序列化的注意事项
- 将CSS放头部,JS放底部,可以提高页面的性能的原因
- C# 根据出生日期(年月日)计算年龄的代码
- Recursion之Demo
- 监控elssticSearch健康状态
- mac java_home等系统参数配置
- MATLAB小波包的分解与重构
- 阿里云CentOS Linux服务器上搭建邮件服务器遇到的问题
- 用户密码管理和 su 命令
- Java枚举的小用法
- 【BZOJ】【2738】&;【Tsinsen】【A1333】矩阵乘法
- 【WPF】对话框/消息弹窗
- CentOS中Ctrl+Z、Ctrl+C、Ctrl+D的区别
热门文章
- linux 关于数据库的部分命令
- AS3获取对象类名,getDefinitionByName,getQualifiedClassName,getQualifiedSuperclassName
- 通过beego快速创建一个Restful风格API项目及API文档自动化(转)
- 推荐的 MongoDB 安装文档
- DELL服务器iDRAC相关设置
- Status Code:405 Method Not Allowed
- function方法控制是否隐藏部分内容
- sshd_config优化
- springmvc DispatchServlet初始化九大加载策略(一)
- obstacle