摘要:维护上凸壳来斜率优化

P3628 [APIO2010]特别行动队

题面

题目分析

首先考虑出一个$O(n^2)$的dp出来(sum为前缀和):

$f_i = max\{f_j + a(sum_i - sum_j)^2 + b(sum_i-sum_j) +c\} (1 \leq j \leq i)$

暴力拆开,整理得:

$f_i = max\{f_j - 2asum_isum_j + asum_j^2 - bsum_j\} + asum_{i}^2 + bsum_i +c$

需要把这个式子化成$y = kx+ b$的形式进行线性规划.

考虑把max后面的一堆东西移到左边,作为线性规划中需要最大化的截距,即$b_i = f_i - asum_{i}^2 - bsum_i - c$.

然后$2asum_i$作为斜率,$sum_j$作为x,$f_j + asum_j^2 - bsum_j$作为y.

所以就可以发现,斜率是单调递减的,$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
#include "iostream"
#include "cstdio"
#include "cstring"
#include "cstdlib"
#include "cmath"
#include "cctype"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "vector"
#include "stack"
#define lxl long long
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define k(i) (2*a*sum[i])
#define x(i) (sum[i])
#define b(i) (f[i]-a*sum[i]*sum[i]-b*sum[i]-c)
#define y(i) (f[i]+a*sum[i]*sum[i]-b*sum[i])
const lxl maxn=1000010;
lxl n,a,b,c,l,r;
lxl sum[maxn],q[maxn],f[maxn];
double k[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)(y(i)-y(j))/(x(i)-x(j));}
int main(void)
{
n=read(),a=read(),b=read(),c=read();
for(R int i(1);i<=n;++i)sum[i]=read()+sum[i-1];
for(R int i(1);i<=n;++i)
{
while(l<r&&slope(q[l],q[l+1])>k(i))++l;
f[i]=-1*(k(i)*x(q[l])-y(q[l])-a*sum[i]*sum[i]-b*sum[i]-c);
while(l<r&&slope(q[r-1],q[r])<=slope(q[r],i))--r;
q[++r]=i;
}
printf("%lld\n",f[n]);
return 0;
}