Bzoj 1096
题意：给定$n$个点间的距离,每个点的物品数和建仓库的花费,每个点的物品可以放在该点建的仓库或它后面点建的仓库,运输的费用为距离乘以物品数
设$dp(i)$为在$i$建仓库的最优解。
由$\sum_{k=j+1}^{i-1}p_k(x_i-x_k)=x_i \sum_{k=j+1}^{i-1}p_k-\sum_{k=j+1}^{i-1}x_kp_k$，得
$dp(i)=min(dp(j)+x_i \sum_{k=j+1}^{i-1}p_k-\sum_{k=j+1}^{i-1}x_kp_k)$
设$G_i=\sum p_k, E_i=\sum x_kp_k$，则
$$dp(i)=dp(j)+x_iG_{i-1}-x_iG_j-E_{i-1}+E_j$$
然后发现又有$i$又有$j$这种的，想到斜率优化。
决策单调性证明略。
假设$i$前有两个决策$j,k$，且$k$比$j$优，则
$$dp(j)+x_iG_{i-1}-x_iG_j-E_{i-1}+E_j > dp(k)+x_iG_{i-1}-x_iG_k-E_{i-1}+E_k$$
将$x_i$移到右边，得
$$x_i > \frac{dp(k)-dp(j)+E_k-E_j}{G_k-G_j}$$
设$k=\frac{dp(k)-dp(j)+E_k-E_j}{G_k-G_j}$，则算出两点斜率方程，当$x_i > k_{kj}$满足时，说明$i$时$k$比$j$优
易错点：
1、que[l]与l分清楚！
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 1000000 + 5;
LL n, xi[MAXN], pi[MAXN], ci[MAXN], G[MAXN], E[MAXN], dp[MAXN], que[MAXN * 4], l, r;
db getK(LL k, LL j) {return (db)(dp[k] - dp[j] + E[k] - E[j]) / (db)(G[k] - G[j]);}
void clean() {}
int solve() {
clean();
G[0] = E[0] = 0;
for (LL i = 1; i <= n; i++) scanf("%lld%lld%lld", &xi[i], &pi[i], &ci[i]), G[i] = G[i - 1] + pi[i], E[i] = E[i - 1] + xi[i] * pi[i];
l = 1, r = 1, dp[0] = 0;
for (LL i = 1; i <= n; i++) {
while (l < r && getK(que[l], que[l + 1]) <= xi[i]) l++;
dp[i] = dp[que[l]] + xi[i] * (G[i - 1] - G[que[l]]) - (E[i - 1] - E[que[l]]) + ci[i];
while (l < r && getK(que[r - 1], que[r]) >= getK(que[r], i)) r--;
que[++r] = i;
}
printf("%lld\n", dp[n]);
return 0;
}
int main() {
scanf("%lld", &n), solve();
return 0;
}
