P3628 [APIO2010] 特别行动队 题解

yyrwlj · 2024-01-11 19:23:45 · 个人记录

题目传送门

蒟蒻的第一篇斜率优化题解。

思路

首先定义状态 f_i 表示前 i 个士兵分组的最大和，也就是 i 和 i+1 中间分开。

根据定义很容易推出 O(n^2) 的转移式子

其中 S_i = \sum_{j=1}^{i}x_i。

去括号，得

容易发现 j 是唯一的变量，原式即

为了使原式转换成 y=kx+B的形式，y=f_j+a{S_j}^2-bS_j，k=2aS_i，B=f_i-a{S_i}^2-bS_i-c，x=S_j。

然后就转换完成了，而且有了新的状态转移方程：

单调队列维护凸壳即可。

斜率优化dp总结

第一步，推出 O(n^2) 复杂度的转移方程。

第二步，去括号、移项，找到唯一的变量 j。

第三步，y 表示只跟 j 有关的项，k 表示跟 i 和 j 都有关的项的不含 j 部分，b 表示常量，x 表示跟 i 和 j 都有关的项的含 j 部分。

第四步，单调队列（特殊情况用其它数据结构，如平衡树）维护凸壳。

最后输出答案。

Code

#include <iostream>
using namespace std;
const int N = 1000005;
typedef long long LL;
LL f[N], s[N];
int q[N], a, b, c;
inline LL k(int i)
{
    return 2 * a * s[i];
}
inline LL x(int i)
{
    return s[i];
}
inline LL y(int i)
{
    return f[i] + a * s[i] * s[i] - b * s[i];
}
double get(int i,int j)
{
    return (double)(y(i) - y(j)) / (x(i) - x(j));
}
int main()
{
    int n;
    scanf("%d%d%d%d", &n, &a, &b, &c);
    for (int i=1;i<=n;i++)
    {
        scanf("%d", &s[i]);
        s[i] += s[i - 1];
    }
    int hh = 0, tt = 0;
    for (int i=1;i<=n;i++)
    {
        while (hh < tt && get(q[hh], q[hh + 1]) > k(i))
            hh ++;
        f[i] = -k(i) * x(q[hh]) + y(q[hh]) + a * s[i] * s[i] + b * s[i] + c;
        while (hh < tt && get(q[tt - 1], q[tt]) <= get(q[tt], i))
            tt --;
        q[++tt] = i;
    }
    printf("%lld", f[n]);
    return 0;
}