「APIO 2010」特别行动队

发表于 | | 阅读次数:
字数统计: 337 字

Description

题目链接：BZOJ 1911

你有一支由 $n$ 名预备役士兵组成的部队，士兵从 $1$ 到 $n$ 编号，要将他们拆分 成若干特别行动队调入战场。出于默契的考虑，同一支特别行动队中队员的编号 应该连续，即为形如 $(i,i+1,\dots,i+k)$ 的序列。 编号为 $i$ 的士兵的初始战斗力为 $x_i$ ，一支特别行动队的初始战斗力 $x$ 为队内 士兵初始战斗力之和，即 $x=x_i+x_{i+1}+\cdots+x_{i+k}$。

通过长期的观察，你总结出一支特别行动队的初始战斗力 $x$ 将按如下经验公 式修正为 $x’$：$x’= ax^2+bx+c$，其中 $a,b,c$ 是已知的系数（$a<0$）。 作为部队统帅，现在你要为这支部队进行编队，使得所有特别行动队修正后战斗力之和最大。试求出这个最大和。

数据范围：$1\le n\le 10^6$，$-5\le a\le -1$，$\vert b\vert,\vert c\vert\le 10^7$，$1\le x_i\le 100$

Solution

我们先列出一个朴素的 $\text{DP}$ 方程，定义 $f_i$ 表示考虑到第 $i$ 个人时的战斗力之和的最大值，记 $sum_i=\sum_{k=1}^i x_k$，那么转移方程为：

直接转移的复杂度是 $O(n^2)$ 的，由于有平方项考虑斜率优化。

根据套路，我们任取 $j,k$ 且 $0\le k<j<i$，如果 $j$ 比 $k$ 更优，那么有：

整理得到（注意题目中保证 $a<0$）：

我们发现，不等式左边是单调递减的，右边分母上的前缀和是单调递增的。

那么我们用单调队列维护一个上凸壳，斜率递减且均小于当前的 $2a\cdot sum_i$，每次的最优决策就是队首。

时间复杂度：$O(n)$

Code

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>

const int N=1e6+5;
int n,A,B,C,a[N],q[N];
long long sum[N],f[N];

long long sqr(long long x) {
    return x*x;
}
double slope(int i,int j) {
    return 1.0*((f[i]+1LL*A*sqr(sum[i])-1LL*B*sum[i])-(f[j]+1LL*A*sqr(sum[j])-1LL*B*sum[j]))/(sum[i]-sum[j]);
}
int main() {
    scanf("%d%d%d%d",&n,&A,&B,&C);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
    int l=1,r=0;
    f[0]=q[++r]=0;
    for(int i=1;i<=n;++i) {
        while(l<r&&slope(q[l],q[l+1])>=2.0*A*sum[i]) ++l;
        f[i]=f[q[l]]+1LL*A*sqr(sum[i]-sum[q[l]])+1LL*B*(sum[i]-sum[q[l]])+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;
}
0%