2018.09.07 bzoj1096: [ZJOI2007]仓库建设(斜率优化dp)
2024-10-21 06:38:08
传送门
斜率优化dp经典题。
令f[i]表示i这个地方修建仓库的最优值,那么答案就是f[n]。
用dis[i]表示i到1的距离,sump[i]表示1~i所有工厂的p之和,sum[i]表示1~i所有工厂的p*dis之和。
那么有状态转移方程:
f[i]=min(f[j]+dis[i]∗(sump[i−1]−sump[j])−(sum[i]−sum[j])+c[i])" role="presentation" style="position: relative;">f[i]=min(f[j]+dis[i]∗(sump[i−1]−sump[j])−(sum[i]−sum[j])+c[i])f[i]=min(f[j]+dis[i]∗(sump[i−1]−sump[j])−(sum[i]−sum[j])+c[i])
于是选两个决策k1,k2并假设k1比k2优。
令t[k]=f[k]+sum[k]" role="presentation" style="position: relative;">t[k]=f[k]+sum[k]t[k]=f[k]+sum[k]
=>(t[k1]−t[k2])/(sump[k1]−sump[k2])>dis[i]" role="presentation" style="position: relative;">(t[k1]−t[k2])/(sump[k1]−sump[k2])>dis[i](t[k1]−t[k2])/(sump[k1]−sump[k2])>dis[i]
于是维护一个下凸壳就行了。
代码:
#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
inline ll read(){
ll ans=0,w=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans*w;
}
int n,q[N],hd,tl;
ll sum[N],sump[N],f[N],dis[N],c[N];
inline double slope(int i,int j){return 1.0*(f[i]+sum[i]-f[j]-sum[j])/(sump[i]-sump[j]);}
int main(){
n=read(),hd=tl=1,q[1]=0;
for(int i=1;i<=n;++i)dis[i]=read(),sump[i]=sump[i-1]+read(),sum[i]=sum[i-1]+dis[i]*(sump[i]-sump[i-1]),c[i]=read();
for(int i=1;i<=n;++i){
while(hd<tl&&slope(q[hd+1],q[hd])<1.0*dis[i])++hd;
int j=q[hd];
f[i]=f[j]+dis[i]*(sump[i-1]-sump[j])-(sum[i-1]-sum[j])+c[i];
while(hd<tl&&slope(q[tl],q[tl-1])>slope(i,q[tl]))--tl;
q[++tl]=i;
}
cout<<f[n];
return 0;
}
最新文章
- easyUI 如何不跳转页面,只是加载替换center部分内容
- 做为一个前端工程师,是往node方面转,还是往HTML5方面转
- [Maven]初次实践
- z-index 可以使用负值,CSS相对定位、绝对定位利器
- python ConfigParser、shutil、subprocess、ElementTree模块简解
- UVALive 6523 Languages
- centos 安装jdk
- Android(java)学习笔记266:Android线程形态之 IntentService
- Excel多条件筛选求和
- 利用正则表达式作为string.split seprator
- 【Error listenerStart】 Error listenerStart Context [] startup failed due to previous errors
- MFC让控件随窗口大小而改变
- ke
- vim下单行长文本的时候卡顿解决办法
- php树形结构数组转化
- node 学习(一)
- html/css 表格元素以及表格布局
- [C++]常识回顾
- (原创)Rocketmq分布式消息队列的部署与监控
- iOS UI基础-21 WKWebView