蒟蒻就写一下简单题吧。。。
此题很容易写出dp的方程：
令f[i]表示i号点要建仓库的话最小总费用，则
f[i] = min(f[j] + (x[i] - x[j + 1]) * p[i + 1] + (x[i] - x[j + 2])* p[i + 2] + ... + (x[i] - x[i]) * p[i]) + c[i]
然后把min里面的东西展开再合并，并且令
sp[i] = p[1] + p[2] + ... + p[i]
s[i] = x[1] * p[1] + x[2] * p[2] + ... + x[i] * p[i]
那么：
f[i] = min(f[j] + s[j] - x[i] * sp[j]) + c[i] + sp[i] * x[i] - s[i];
然后前面的min里的式子可以斜率优化掉，就做完了。（我好像会自己推了?进步+1^_^）
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 long long q[1200000], s[1200000], sp[1200000], f[1200000], g[1200000]; 8 long long x; 9 int l = 1, r = 1, n;10 11 inline bool pop_head(){12 int a = q[l], b = q[l + 1];13 return (long long) g[b] - g[a] < (long long)x * (sp[b] - sp[a]);14 }15 16 inline bool pop_tail(int i){17 int a = q[r - 1], b = q[r];18 return (long long) (g[b] - g[a]) * (sp[i] - sp[b]) >= (long long) (g[i] - g[b]) * (sp[b] - sp[a]);19 }20 21 int main(){22 scanf("%d\n", &n);23 long long p, c;24 q[1] = 0;25 int j;26 for (int i = 1; i <= n; ++i){27 scanf("%lld %lld %lld\n", &x, &p, &c);28 sp[i] = sp[i - 1] + p;29 s[i] = s[i - 1] + x * p;30 while (l < r && pop_head()) ++l;31 j = q[l];32 f[i] = g[j] - x * sp[j] + c + sp[i] * x - s[i];33 g[i] = f[i] + s[i];34 while (l < r && pop_tail(i)) --r;35 q[++r] = i;36 }37 printf("%lld\n", f[n]);38 return 0;39 }
(p.s. 沙茶的我把q写成g，结果WA了两次。。。)