【题解】BZOJ 1911 [APIO2010]特别行动队

Problem

给定一个长度为 $n$ 序列 $x$ ,请将其分为连续的若干段,定义一段的权值为

$$ s_i=\sum_{i=l}^{r}x_i $$

最大化

$$ \sum_{i}as_i^2+bs_i+c $$

Thought

考虑设将前 $i$ 个人分组的最大贡献为 $f[i]$, 有如下转移方程:

$$ f[i]=\max\{f[j]+a*sum[j+1,i]^2+b*sum[j+1,i]+c\}(j<i) $$

假设当前有两个决策 $j,k$ ,其中 $j<k$

$$ f[j]+a*sum[j+1,i]^2+b*sum[j+1,i]+c\\ f[k]+a*sum[k+1,i]^2+b*sum[k+1,i]+c $$

证明决策单调性:

$$ f[k]+a*sum[k+1,i]^2+b*sum[k+1,i]+c\\ \ge\\ f[j]+a*sum[j+1,i]^2+b*sum[j+1,i]+c $$

$sum[k+1,i]=sum[i]-sum[k]$,将平方项打开,消去,可得

$$ f[k]-2a*sum[k]*sum[i]+a*sum[k]^2-b*sum[k]\\ \ge\\ f[j]-2a*sum[j]*sum[i]+a*sum[j]^2-b*sum[j] $$

设 $g[i]=f[i]+a*sum[i]^2-b*sum[i]$

那么有

$$ g[k]-2a*sum[k]*sum[i]\ge g[j]-2a*sum[j]*sum[i] $$

移项可得

$$ g[k]-g[j]\ge 2a*sum[i]*(sum[k]-sum[j])\\ \frac{g[k]-g[j]}{sum[k]-sum[j]}\ge2a*sum[i] $$

这就转化为了一般的斜率式,由于 $2a*sum[i]$ 单调下降,所以可以用栈来维护当前的决策

时间复杂度 $O(n)$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read() {
    ll ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 1000010;
int n;
ll sum[N], f[N];
int q[N], head, tail;
double g[N];
ll A, B, C;
double slope(int a, int b) {
    return (g[b] - g[a]) / (sum[b] - sum[a]);
}
int main() {
    n = read();
    A = read(); B = read(); C = read();
    for(int i = 1; i <= n; ++ i)
        sum[i] = sum[i - 1] + read();
    head = 0, tail = 0;
    for(int i = 1; i <= n; ++ i) {
        while(head < tail && slope(q[head], q[head + 1]) >= 2 * A * sum[i]) ++ head;
        int t = q[head];
        int s = sum[i] - sum[t];
        f[i] = f[t] + A * s * s + B * s + C;
        g[i] = f[i] + A * sum[i] * sum[i] - B * sum[i];
        while(head < tail && slope(q[tail - 1], q[tail]) < slope(q[tail], i)) q[tail --] = 0;
        q[++ tail] = i;
    }
    printf("%lld\n", f[n]);
    return 0;
}
Comments

添加新评论