P3628:[APIO2010]特别行动队题解 & 斜率优化分析

暴力做法

我们首先来推下这道题普通的 DP 方程,显而易见,维护前缀和后,在\(f[i]\)时枚举一个点\(j\)划分即可:

\[ f[i] = max_{j\in [1,i-1]} \{f[j]+a(S[i]-S[j])^2+b(S[i]-S[j])+c\} \]

时间复杂度为\(O(n^2)\),GG。

斜率优化分析

第一步 – 写出斜率方程

这是所有斜率优化题目分析的第一步:给定两个量\(j_1<j_2\),写出斜率不等式得出单调关系。这一步进行参变分离即可,稍稍有点麻烦。

我们以本题为例,进行斜率方程的推导:

\[ f[j_1]+a(S[i]-S[j_1])^2+b(S[i]-S[j_1])+c>f[j_2]+a(S[i]-S[j_2])^2+b(S[i]-S[j_2])+c \\ (f[j_1]-f[j_2])+a(S[j_1]^2-S[j_2]^2)+b(S[j_2]-S[j_1])>2a(S[j_1]-S[j_2])*S[i] \\ \frac{(f[j_1]-f[j_2])+a(S[j_1]^2-S[j_2]^2)+b(S[j_2]-S[j_1])}{2a(S[j_1]-*S[j_2])}>S[i] \]

注意\(a<0\)

第二步 – 队头的弹出条件

我们观察这个方程,当\(j_2\)比\(j_1\)更优时:

\[ \frac{(f[j_1]-f[j_2])+a(S[j_1]^2-S[j_2]^2)+b(S[j_2]-S[j_1])}{2a(S[j_1]-S[j_2])} \leq S[i] \]

因为\(S[i]\)随着\(i\)单调不下降,所以当\(j_2\)比\(j_1\)更优时,\(j_1\)永远不会被考虑,弹出。

第三步 – 队头转移

这个没什么好说的,直接将\(q[head]\)当做\(j\)来用即可。

第四步 – 队尾的处理

我们还需要保证这些直线斜率的单调性。首先,以本题为例,我们来对斜率单调性进行分析。

我们假设斜率函数为\(slope(j_1,j_2)\),函数的解析式就是我们上面推出来的式子,即:

\[ slope(j_1, j_2) = \frac{(f[j_1]-f[j_2])+a(S[j_1]^2-S[j_2]^2)+b(S[j_2]-S[j_1])}{2a(S[j_1]-S[j_2])} \]

我们假设直线的斜率必须要单调递增,也就是\(l<mid<r, slope(l,mid)<slope(mid,r)\)。我们在单调队列中只保留可能成为最优解的选项,也就是对于元素\(a_1,a_2,a_3\),\(a_1\)比\(a_2\)更优且\(a_2\)比\(a_3\)更优。所以,中间我们有:

\[ slope(l,mid)>S[i] \text{且} slope(mid,r)<S[i] \]

整理得:

\[ slope(l,mid)>slope(mid,r) \]

与假设相反。所以,我们处理队尾的时候其实就是在维护这个关系,所以弹出条件就是“如果这个斜率是单调递增的”:

\[ l<mid<r, slope(l,mid)<slope(mid,r) \]

所以,分析完毕。

代码

// P3628.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 1e6 + 2000;
ll n, xi[MAX_N], a, b, c, S[MAX_N], f[MAX_N], q[MAX_N], head, tail;
ll pow(ll num) { return num * num; }
double slope(int j1, int j2)
{
    return double((f[j1] - f[j2] + b * (S[j2] - S[j1]) + a * (pow(S[j1]) - pow(S[j2])))) / double(2 * a * (S[j1] - S[j2]));
}
int main()
{
    scanf("%lld%lld%lld%lld", &n, &a, &b, &c);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &xi[i]), S[i] = S[i - 1] + xi[i];
    head = 1, tail = 1;
    for (int i = 1; i <= n; i++)
    {
        while (head < tail && slope(q[head], q[head + 1]) <= S[i] * 1.0)
            head++;
        f[i] = f[q[head]] + a * pow(S[i] - S[q[head]]) + b * (S[i] - S[q[head]]) + c;
        while (head <= tail && slope(q[tail - 1], q[tail]) >= slope(q[tail], i))
            tail--;
        q[++tail] = i;
    }
    printf("%lld", f[n]);
    return 0;
}

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注