题目传送门(BZOJ)
>原文链接<

题解 :

三倍经验

本题Dp的方程比较好推导,我们设两个数组,sum对货物量进行前缀求和、sum1对前i-1个仓库的货物都运到i的代价进行求和

F[i]为在i点建仓库的总最小花费。

那么DP方程显然为F[i]=\min{ f[j] + sum1[i] – sum1[j] – sum[j] \times(x[i] – x[j]) + c[i]}

考虑斜率优化 。 对上式进行化简得

F[i]-c[i] – sum1[i] = F[j] – sum1[j] – sum[j] \times x[j] + s[j] \times x[i]

我们设

B(j) = F[j] + x[j] \times s[j] -sum1[j]

K(j)= -sum[j]

Y(i,j)= K(j)\times x[i] + B(j) = F[i] – c[i] – sum1[i]

F[i] = Y(i,j) + sum1[i] + c[i]

考虑单调性 K(j) 单调递减x[i]单调递增。维护直线就是一般的单调队列了。

BZOJ 3437 只是把x[i]变成了i,其他的没有变化

而BZOJ 3156 只是在3437的基础上把sum[i]变成i,其他的没有变化。

代码 (1096):

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N = 1200000;#define int long long#define ll long long#define K(i) (-s[i])#define B(i) (f[i]+x[i]*s[i]-s1[i])#define Y(i, j) (K(j)*x[i]+B(j))int x[N], p[N], c[N], s[N], s1[N], f[N];int q[N], l, r;bool cmp(int i,int j,int k) { ll x1=(K(i)-K(k))*(B(j)-B(i)); ll x2=(K(i)-K(j))*(B(k)-B(i)); return x1>=x2;}signed main() { int n; scanf("%d",&n); for(int i = 1; i <= n; i ++ ) { scanf("%lld%lld%lld",&x[i],&p[i],&c[i]); s[i]=s[i-1]+p[i]; s1[i]=s1[i-1]+s[i-1]*(x[i]-x[i-1]); } for(int i = 1; i <= n; i ++ ) { while(l < r && Y(i, q[l]) >= Y(i, q[l+1])) l++; f[i] = Y(i,q[l])+s1[i]+c[i]; while(l < r&& cmp(i, q[r-1], q[r])) r--; q[++r] = i; } printf("%lld\n", f[n]);}