0%

Project2120_[ZJOI2007]仓库建设项目报告

摘要:斜率优化dp

P2120 [ZJOI2007]仓库建设

题面

题目分析

设$f_i$表示第i个位置建仓库,i上面所有工厂的物质转移完毕所需的最小代价.

先搞一个$O(n^3)$的大力dp,如下:

$f_i = min \{ f_j + \sum_{l=j+1}^{i}((x_i-x_l)*p_l) \} + c_i \qquad (1 \leq j < i)$

发现和式是可以拆的,化为下式:

$f_i = min \{ f_j + x_i \sum_{l=j+1}^{i}p_l - \sum_{l=j+1}^{i}x_lp_l \} + c_i \qquad (1 \leq j < i)$

然后就可以用前缀和优化为:

$f_i = min \{ f_j + (sump_i - sump_j) * x_i - (sum_i -sum_j)\} + c_i \qquad (1 \leq j < i)$

发现式子的形式可以斜率优化,设用k转移i比用j转移i优秀,得到如下不等式:

$f_k + (sump_i - sump_k) x_i - (sum_i - sum_k) < f_j +(sump_i - sump_j) x_i - (sum_i - sum_j)$

移项,整理得:

$\frac{(f_k + sum_k)-(f_j + sum_j)}{sump_k -sump_j} < x_i$

$f_i + sum_i$作为y,$sump_i$作为x单调增加,$x_i$作为斜率单调增加,维护一个上凸壳.

代码

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include "iostream"
#include "cstdio"
#include "cstring"
#include "cstdlib"
#include "cmath"
#include "cctype"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "vector"
#define lxl long long
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
const lxl maxn=1000010;
lxl n,l,r;
lxl sump[maxn],sum[maxn],x[maxn],c[maxn],f[maxn],q[maxn];
inline lxl read()
{
char c=getchar();
lxl f=1,x=0;
for(;!isdigit(c);c=getchar())(c=='-')&&(f=-1);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f*x;
}
inline double slope(lxl a,lxl b)
{
lxl ya=f[a]+sum[a],yb=f[b]+sum[b];
lxl xa=sump[a],xb=sump[b];
return (double)(yb-ya)/(double)(xb-xa);
}
int main(void)
{
n=read();
for(R int i(1);i<=n;++i)
{
x[i]=read(),sump[i]=read(),c[i]=read();
sum[i]=x[i]*sump[i]+sum[i-1];
sump[i]+=sump[i-1];
}
for(R int i(1);i<=n;++i)
{
while(l<r&&slope(q[l],q[l+1])<x[i])++l;
f[i]=f[q[l]]+(sump[i]-sump[q[l]])*x[i]-(sum[i]-sum[q[l]])+c[i];
while(l<r&&slope(q[r-1],q[r])>slope(q[r],i))--r;
q[++r]=i;
}
printf("%lld\n",f[n]);
return 0;
}