斜率优化DP
记pre[i]为p[i]的前缀和，s[i]为1~i的物品全部运到i的花费，然后可以弄出一个方程，接着就可以发现斜率优化。
下午脑子不太清楚方程写错+程序打错 吃枣药丸。。。
#include<cstdio> #define N 1000005 #define ll long long #define TEMP N-1 using namespace std; ll f[N], pre[N], d[N], s[N], c[N], x[N], y[N]; bool calc(int a, int b, int c) { return (x[b]-x[a])*(y[c]-y[a])-(x[c]-x[a])*(y[b]-y[a])>=0; } int main() { int n; scanf("%d",&n); for(int i = 1; i <= n; i++) { scanf("%lld%lld%lld",&d[i],&pre[i],&c[i]); s[i]=s[i-1]+pre[i-1]*(d[i]-d[i-1]); pre[i]+=pre[i-1]; } int head=0, tail=0; x[tail]=0; y[tail++]=0; for(int i = 1; i <= n; i++) { while(tail-head>1 && y[head]-y[head+1]<1.0*(x[head]-x[head+1])*(-d[i]))head++; f[i]=-d[i]*x[head]-y[head]+s[i]+c[i]; x[TEMP]=pre[i]; y[TEMP]=-f[i]+s[i]-pre[i]*d[i]; while(tail-head>1 && calc(tail-2,tail-1,TEMP))tail--; x[tail]=x[TEMP]; y[tail++]=y[TEMP]; } printf("%lld\n",f[n]); return 0; }