BZOJ 1096.「ZJOI2007」仓库建设

我们可以把问题抽象一下:
把一个序列划分成若干段,如果某一段对应的区间为 [l,r][l,r],则代价为 cr+i=lrpi(xrxi)c_r + \sum\limits_{i = l}^r p_i(x_r - x_i)
于是得到转移方程 fi=min0j<i(fj+ci+k=j+1ipk(xixk))f_i = \min\limits_{0 \le j < i}(f_j + c_i + \sum\limits_{k = j + 1}^i p_k(x_i - x_k))

si=j=1ipi,Si=j=1ipixis_i = \sum\limits_{j = 1}^i p_i,S_i = \sum\limits_{j = 1}^i p_ix_i
则原式变为 fi=min0j<i(fj+ci+(sisj)xi(SiSj))f_i = \min\limits_{0 \le j < i}(f_j + c_i + (s_i - s_j) x_i - (S_i - S_j))

对于 0k<j<i0 \le k < j < i,设此时选择 jj 更优,即 fj+ci+(sisj)xi(SiSj)fk+ci+(sisk)xi(SiSk)f_j + c_i + (s_i - s_j) x_i - (S_i - S_j) \le f_k + c_i + (s_i - s_k) x_i - (S_i - S_k)
整理一下,有

单调队列维护下凸包即可。

代码:

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
#include <cstdio>
using namespace std;
const int N = 1e6;
int n;
int q[N + 5],head,tail;
int x[N + 5],p[N + 5],c[N + 5];
long long s[N + 5],S[N + 5],f[N + 5];
inline double slope(int x,int y)
{
return (double)(f[x] + S[x] - f[y] - S[y]) / (s[x] - s[y]);
}
int main()
{
scanf("%d",&n);
for(register int i = 1;i <= n;++i)
scanf("%d%d%d",x + i,p + i,c + i),s[i] = s[i - 1] + p[i],S[i] = S[i - 1] + (long long)p[i] * x[i];
q[head = tail = 1] = 0;
for(register int i = 1;i <= n;++i)
{
for(;head < tail && slope(q[head],q[head + 1]) <= x[i];++head);
f[i] = f[q[head]] + c[i] + (s[i] - s[q[head]]) * x[i] - S[i] + S[q[head]];
for(;head < tail && slope(q[tail - 1],q[tail]) >= slope(q[tail],i);--tail);
q[++tail] = i;
}
printf("%lld\n",f[n]);
}