LibreOJ 10192.「CEOI2004」锯木厂选址

首先写出朴素的式子:fi=min1j<i(costsumjdisj(sumisumj)disi)f_i = \min\limits_{1 \le j < i} (cost - sum_j dis_j - (sum_i - sum_j)dis_i)
其中 fif_i 表示第二个锯木厂建在 ii 处的最小代价,sumi=j=1iwj,disi=j=indjsum_i = \sum\limits_{j = 1}^i w_j,dis_i = \sum\limits_{j = i}^n d_jcostcost 表示只有山脚的锯木厂的代价。
这貌似不是个 DP?不过也可以用斜率优化解决!

对于 1k<j<i1 \le k < j < i,假设选 jj 优于选 kk,即

按照套路,单调队列维护上凸包即可。

代码:

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
#include <cstdio>
#include <algorithm>
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);
}