摘要:另一种思考方式下的斜率优化

P4360 [CEOI2004]锯木厂选址

题面

题目分析

先求出距离的后缀和d数组,树重量的前缀和s,因为是从上到下运,所以用上面的重量和乘以下面的距离和,然后求出如果不修工厂需要的花费总和sum.

考虑一个$O(n^2)$的dp,$f_i$表示第2个工厂修在i号位置时的最优解,向前枚举第1个工厂,得到如下方程:

$f_i = sum - s_{j}d_{j} - d_{i}(s_i-s_j)$

用另一种方式来考虑斜率优化,设在i点的转移时,用k转移比用j转移优秀,即:

$sum - s_{k}d_{k} - d_{i}(s_i-s_k) < sum - s_{j}d_{j} - d_{i}(s_i-s_j)$

化简得:

$\frac{s_jd_j-s_kd_k}{s_j-s_k} > d_i$

$d_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
#include "iostream"
#include "cstdio"
#include "cstring"
#include "cstdlib"
#include "cmath"
#include "cctype"
#include "algorithm"
#include "set"
#include "queue"
#include "stack"
#include "vector"
#include "map"
#define lxl long long
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
const lxl maxn=20010;
lxl n,sum,l,r,ans=INF;
lxl w[maxn],d[maxn],s[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 i,lxl j){return (double)(d[i]*s[i]-d[j]*s[j])/(s[i]-s[j]);}
inline lxl GetAns(lxl i,lxl j){return sum-d[j]*s[j]-d[i]*(s[i]-s[j]);}
int main(void)
{
n=read();
for(R int i(1);i<=n;++i)w[i]=read(),d[i]=read();
for(R int i(n);i;--i)d[i]+=d[i+1];
for(R int i(1);i<=n;++i)s[i]=s[i-1]+w[i],sum+=d[i]*w[i];
for(R int i(1);i<=n;++i)
{
while(l<r&&slope(q[l],q[l+1])>d[i])++l;
ans=std::min(ans,GetAns(i,q[l]));
while(l<r&&slope(q[r-1],q[r])<slope(q[r],i))--r;
q[++r]=i;
}
printf("%lld\n",ans);
return 0;
}