【笔记篇】斜率优化dp(四) ZJOI2007仓库建设
2024-09-01 22:43:50
传送门戳这里>>>
\(n\leq1e6\), 显然还是\(O(n)\)的做法.
这个题有个条件是只能运往编号更大的工厂的仓库, 这也是写出朴素dp的方程的条件.
我们令\(f[i]\)表示前\(i\)个工厂的最小花费, 那么易得
\[f[i]=min\{f[j]+t(j,i)\}
\]
\]
其中这个\(t(j,i)\)表示将\((j,i)\)这个区间的东西运到\(i\)的总费用. 很显然, 这个式子要\(O(1)\)求出来才行, 不然复杂度就要炸...
那么怎么\(O(1)\)求呢?
考虑类似于前缀和的性质.
我们令\(s_i\)为将\((1,i]\)这个区间中所有工厂的产品运到\(i\)的总花费, \(c_i\)表示前\(i\)个工厂的产品总量, \(d_i\)表示第\(i\)个工厂的坐标, 我们发现, 如果对\(i,j\)做一波前缀和相减, 那么前\(j\)个点的货物都被多运了\(d_i-d_j\)的距离... 所以就可以推出
\[t(j,i)=s_i-s_j-c_j*(d_i-d_j)
\]
\]
这样就可以扔进状态转移方程进行斜率优化了... 化完之后的式子是:
\(f[j]-s[j]+c[j]*d[j]\)=\(d[i]\)\(c[j]\)+\(f[i]-s[i]-w[i]\)
然后求的是最小值, 斜率还递增(这好像是最常见的一种了吧?), 那就跟之前一样咯= =
然而还是把演草纸上\(d[i],c[j]\)的数组名抄反了WA了一次 但为什么可以过样例啊QAQ
然后就是没有压行的代码: (简单的斜率优化似乎总可以写成标准的20行?
#include <cstdio>
const int N=1e6+6;
typedef long long LL;
LL f[N],s[N],c[N];
int q[N],w[N],d[N],n,h,t;
inline int gn(int a=0,char c=0){
for(;c<'0'||c>'9';c=getchar());
for(;c>47&&c<58;c=getchar())a=a*10+c-48;return a;
}
double slope(int x,int y){
return 1.0*(f[x]-s[x]+c[x]*d[x]-f[y]+s[y]-c[y]*d[y])/(c[x]-c[y]);
}
int main(){
n=gn(); for(int i=1;i<=n;++i){
d[i]=gn();c[i]=c[i-1]+gn();w[i]=gn();
s[i]=s[i-1]+c[i-1]*(d[i]-d[i-1]);
}
for(int i=1,j;i<=n;++i){
while(h<t&&slope(q[h],q[h+1])<=d[i]) ++h; j=q[h];
f[i]=f[j]+s[i]-s[j]-c[j]*(d[i]-d[j])+w[i];
while(h<t&&slope(q[t],q[t-1])>=slope(q[t],i)) --t;
q[++t]=i;
}
printf("%lld\n",f[n]);
}
最新文章
- C#遍历DataSet中数据的几种方法总结
- Android触摸事件流程剖析
- 欧拉回路(hdu3018)
- Q_OBJECT
- BZOJ 1013 &; 高斯消元
- cell长按出错
- 【20160924】GOCVHelper MFC增强算法(4)
- VB中的属性、方法和事件概念解析
- python打包成exe(py2exe)
- eclipse中输入的中文为繁体的问题
- Android——用户登陆及用户名和密码的保存
- Mysql密码忘记后如何重设密码
- String ua = request.getHeader(";user-agent";)---ua值为null
- C# Excel写入数据及图表
- opensslBIO系列之2---BIO结构和BIO相关文件介绍
- SpringCloud实战-Zuul网关服务
- Windows7下安装pyspark
- react-native-echarts在打包时出现的坑
- asp.net core 系列 9 环境(Development、Staging 、Production)
- sqlserver 游标使用
热门文章
- 大数运算之 Java BigInteger 的基本用法
- PHPStorm IDE 快捷键(MAC版)
- 网络编程(二)——TCP协议、基于tcp协议的套接字socket
- 10 个轻松学会 CSS3 的优秀在线资源
- 看了Google编码规范,我突然有个感觉
- 我要多开梦幻手游PC端(梦幻手游PC端多开的简单分析及实现办法)(二)
- C语言指针函数和函数指针
- Kafka命令行操作
- NX二次开发-遍历当前part所有component,把装配子部件设置成工作部件
- NX二次开发-NXOPEN创建工程图表格Annotations::TableSectionBuilder *tableSectionBuilder1;