首页 > 代码库 > BZOJ 1096 [ZJOI2007]仓库建设（斜率优化DP）
BZOJ 1096 [ZJOI2007]仓库建设（斜率优化DP）
【题目链接】 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;}
BZOJ 1096 [ZJOI2007]仓库建设（斜率优化DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。