首先写出朴素的式子：\(f_i = \min\limits_{1 \le j < i} (cost - sum_j dis_j - (sum_i - sum_j)dis_i)\)。
其中 \(f_i\) 表示第二个锯木厂建在 \(i\) 处的最小代价，\(sum_i = \sum\limits_{j = 1}^i w_j,dis_i = \sum\limits_{j = i}^n d_j\)，\(cost\) 表示只有山脚的锯木厂的代价。
这貌似不是个 DP？不过也可以用斜率优化解决！
对于 \(1 \le k < j < i\)，假设选 \(j\) 优于选 \(k\)，即 \[\begin{align*} cost - sum_jdis_j - (sum_i - sum_j)dis_i & \le cost - sum_kdis_k - (sum_i - sum_k)dis_i \\ sum_jdis_j + (sum_i - sum_j)dis_i & \ge sum_kdis_k + (sum_i - sum_k) dis_i \\ sum_jdis_j + sum_idis_i - sum_jdis_i & \ge sum_kdis_k + sum_idis_i - sum_kdis_i \\ sum_jdis_j - sum_jdis_i & \ge sum_kdis_k - sum_kdis_i \\ sum_jdis_j - sum_kdis_k & \ge (sum_j - sum_k)dis_i \\ \dfrac{sum_jdis_j - sum_kdis_k}{sum_j - sum_k} & \ge dis_i \end{align*}\]
按照套路，单调队列维护上凸包即可。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
using namespace std;
const int N = 2e4;
int n;
int q[N + 5],head,tail;
long long sum[N + 5],dis[N + 5],cost,f[N + 5],ans = 0x3f3f3f3f3f3f3f3f;
inline double slope(int x,int y)
{
return (double)(sum[x] * dis[x] - sum[y] * dis[y]) / (sum[x] - sum[y]);
}
int main()
{
scanf("%d",&n);
for(register int i = 1;i <= n;++i)
scanf("%lld%lld",sum + i,dis + i),sum[i] += sum[i - 1];
for(register int i = n;i;--i)
dis[i] += dis[i + 1],cost += (sum[i] - sum[i - 1]) * dis[i];
q[head = tail = 1] = 1;
for(register int i = 2;i <= n;++i)
{
for(;head < tail && slope(q[head],q[head + 1]) >= dis[i];++head);
ans = min(ans,f[i] = cost - sum[q[head]] * dis[q[head]] - (sum[i] - sum[q[head]]) * dis[i]);
for(;head < tail && slope(q[tail - 1],q[tail]) <= slope(q[tail],i);--tail);
q[++tail] = i;
}
printf("%lld\n",ans);
}