BZOJ 1096 [ZJOI2007]仓库建设(斜率优化DP)
2024-10-09 11:36:08
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1096
【题目大意】
有个斜坡,有n个仓库,每个仓库里面都有一些物品,物品数目为p,仓库位置为x,修缮仓库需要的费用为c,现在下雨了,之后修缮的仓库才能放东西,别的地方的仓库要运东西过来,但是只能往比它地势低的运,问所有物品得到保障的最小代价。
【题解】
显然可以从高处往低处做DP,dp[i]=min(dp[j]+cost(i,j))
我们记s[i]为p[i]的前缀和,b[i]为x[i]*p[i]的前缀和
那么有dp[i]=min(dp[j]+(s[i]-s[j])*x[i]-(b[i]-b[j])+c[i])
当j>k且j比k更优时有:dp[j]-dp[k]+b[j]-b[k]<(sum[j]-sum[k])*x[i],可斜率优化。
【代码】
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=1000010;
int n,l,r,q[N];
ll p[N],x[N],c[N],dp[N],b[N],s[N];
double slop(int k,int j){return double(dp[j]-dp[k]+b[j]-b[k])/double(s[j]-s[k]);}
int main(){
scanf("%d\n",&n);
for(int i=1;i<=n;i++)scanf("%lld%lld%lld",&x[i],&p[i],&c[i]);
for(int i=1;i<=n;i++){s[i]=s[i-1]+p[i];b[i]=b[i-1]+p[i]*x[i];}
for(int i=1;i<=n;i++){
while(l<r&&slop(q[l],q[l+1])<x[i])l++;
int t=q[l];
dp[i]=dp[t]-b[i]+b[t]+(s[i]-s[t])*x[i]+c[i];
while(l<r&&slop(q[r-1],q[r])>slop(q[r],i))r--;
q[++r]=i;
}return printf("%lld",dp[n]),0;
}
最新文章
- Spring框架概述
- 一个C++版的嵌入式操作系统
- Shell 快捷键
- ORACLE执行详解
- LeetCode-Sort Colors
- Mysql常用数据类型
- as的Enter_Frame与Timer
- 关于javax.crypto.BadPaddingException: Blocktype错误的几种解决方法
- hexo常用命令笔记
- BZOJ 3479: [Usaco2014 Mar]Watering the Fields(最小生成树)
- mysql如何执行关联查询与优化
- “你什么意思”之基于RNN的语义槽填充(Pytorch实现)
- 集合之TreeMap(含JDK1.8源码分析)
- Confluence 6 导入模板的步骤
- jQuery插件slider实现图片轮播
- Oracle数据库三种备份方案
- webpack快速入门——CSS进阶,Less文件的打包和分离
- [Swift实际操作]七、常见概念-(2)点CGPoint和变形CGAffineTransform的使用
- 服务器返回的“未在本地计算机上注册“Microsoft.ACE.OLEDB.12.0提供程序””错误解决
- selenium grid应用1-多浏览器执行用例