(Solution) 1
这道题不算很难，这里我提供两种做法。
设 dp[i] 为在 i 位上设置仓库，前面工厂都解决了的最小花费。首先我们可以列出 DP 式：
[dp[i]=min(dp[j]+sigma(p[k]*(x[i]-x[k])))+c[i]
]
即
[dp[i]=min(dp[j]+x[i]*sigma(p[k])-sigma(p[k]*x[k]))+c[i]
]
我们定义 pre 数组为 p 数组的前缀和，s 数组为 (p[i]*x[i]) 的前缀和。用这两个数组乱搞就可以用斜率优化了。
(Code) 1
贴一下代码。
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
int n, q[N], head, tail;
ll c[N], x[N], pre[N], dp[N], s[N];
int read() {
int x = 0, f = 1; char s;
while((s = getchar()) < '0' || s > '9') if(s == '-') f = -1;
while(s >= '0' && s <= '9') {x = (x << 1) + (x << 3) + (s ^ 48); s = getchar();}
return x * f;
}
double slope(const int j1, const int j2) {
return 1.0 * (dp[j2] + s[j2] - dp[j1] - s[j1]) / (pre[j2] - pre[j1]);
}
int main() {
n = read();
for(int i = 1; i <= n; ++ i) {
x[i] = read(), pre[i] = read(), c[i] = read();
s[i] = s[i - 1] + x[i] * pre[i]; pre[i] += pre[i - 1];
}
for(int i = 1; i <= n; ++ i) {
while(head < tail && slope(q[head], q[head + 1]) < x[i]) ++ head;
int j = q[head];
dp[i] = dp[j] + x[i] * (pre[i] - pre[j]) - (s[i] - s[j]) + c[i];
while(head < tail && slope(q[tail], i) < slope(q[tail - 1], q[tail])) -- tail;
q[++ tail] = i;
}
ll ans = dp[n];
printf("%lld
", ans);
return 0;
}
这里说一下一个疑惑。我们 dp[n] 的定义是保证 n 一定会是仓库的最小值。但是，题目并不保证工厂 n 的材料不为 0。也就是说，我们有可能选取之前的 dp 值，保证那个坐标的后面工厂都没有材料（也就不需要设置仓库了）。
我是这样写的：
ll ans = dp[n];
for(int i = n; i >= 1; -- i) {
if(pre[i] - pre[i - 1]) break;
ans = min(ans, (long long) dp[i - 1]);
}
printf("%lld
", ans);
HYSBZ 交上去是错的？好懵？？？（我怀疑是数据有锅或者是我想错了）
(Solution) 2
这是我自己的方法， Luogu 可以过，只是 HYSBZ 过不去 QwQ。（应该是爆 long long 了，如果不是请大佬在评论区指教）
dp 数组，pre 数组定义同上。这里的 s 数组有点不一样，表示前面所有工厂的材料都转移到 i 工厂的花费。则可以转化为：
[dp[i]=min(dp[j]+s[i]-pre[j]*(x[i]-x[j])-s[j])+c[i]
]
其中 (s[i]-pre[j]*(x[i]-x[j])-s[j]) 是将之前的 sigma 感性理解：i 与区间 ([j+1,i]) 的数匹配，每个地方向 i 的花费。我们首先 (s[i]-s[j])，剩下的就是 [1,j] 区间到 i 的花费要减去，而 (pre[j]*(x[i]-x[j])) 正是区间的成品数量乘上路程。
我们设 (f[i]=s[i]) ，(g[i]=pre[i]*x[i]-s[i])，然后乱搞出斜率优化？
(Code) 2
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1e6 + 5;
int n, q[N], head, tail;
double c[N], x[N], pre[N], g[N], dp[N], s[N];
int read() {
int x = 0, f = 1; char s;
while((s = getchar()) < '0' || s > '9') if(s == '-') f = -1;
while(s >= '0' && s <= '9') {x = (x << 1) + (x << 3) + (s ^ 48); s = getchar();}
return x * f;
}
double slope(const int j1, const int j2) {
return (dp[j2] + g[j2] - dp[j1] - g[j1]) / (pre[j2] - pre[j1]);
}
int main() {
n = read();
for(int i = 1; i <= n; ++ i) {
x[i] = read(), pre[i] = read(), c[i] = read();
pre[i] += pre[i - 1]; s[i] = s[i - 1] + 1.0 * (x[i] - x[i - 1]) * pre[i - 1];
g[i] = pre[i] * x[i] - s[i];
}
for(int i = 1; i <= n; ++ i) {
while(head < tail && slope(q[head], q[head + 1]) < x[i]) ++ head;
dp[i] = dp[q[head]] + s[i] - pre[q[head]] * (x[i] - x[q[head]]) - s[q[head]] + c[i];
while(head < tail && slope(q[tail], i) < slope(q[tail - 1], q[tail])) -- tail;
q[++ tail] = i;
}
long long ans = dp[n];
for(int i = n; i >= 1; -- i) {
if(pre[i] - pre[i - 1]) break;
ans = min(ans, (long long) dp[i - 1]);
}
printf("%lld
", ans);
return 0;
}
如果有错误，请大佬在评论区留言哟！