A – 漆黑列车载运数个谎言

这道题应该是并查集域的裸题，不讲。

// A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 200;
int n, m, fa[MAX_N << 2];
int find(int x) { return fa[x] == x ? fa[x] : fa[x] = find(fa[x]); }
void unite(int x, int y) { fa[find(x)] = fa[find(y)]; }
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= 2 * n; i++)
        fa[i] = i;
    while (m--)
    {
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        if (opt == 0)
            unite(x, y), unite(x + n, y + n);
        else if (opt == 1 || opt == 2)
            unite(x, y + n), unite(x + n, y);
        else if (find(x) == find(y) || find(x + n) == find(y + n))
            puts("1");
        else
            puts("0");
    }
    return 0;
}

Continue reading →

暴力做法

我们首先来推下这道题普通的 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;
}

Introduction

有的时候我们在日常写题时，会碰见这样的毒瘤 DP 题目，他们一般有以下特性：

• 多维度动态规划
• 循环层数很多，在极限数据下无法 AC。
• 一般出现在区间 DP 中，一般暴力算法复杂度为\(O(n^3)\)。

这个时候我们可以使用单调队列来优化，时间复杂度可以进一步降至\(O(n^2)\)或者是\(O(nm)\)。如果有不会单调队列的同学呢可以去学习以下，顺便可以看看这篇文章：CH1201:最大子序和题解

Overall on this optimization technique

我们来看一道例题：Fence – POJ这道题是一道比较简单的经典 DP。设计状态\(dp[i][j]\)表示前\(i\)个人搞定了前\(j\)个单位的墙。写出方程式：

\[dp[i][j] = min_{S_i – l_i \leq k < S_i}\{dp[i-1][k]+profit_i*(j-k)\}\]

这样的话，整个算法的复杂度是\(O(n^3)\)的。我们能不能将其降为\(O(n^2)\)呢？我们可以把整个方程变个形，之后方程是这样的：

\[dp[i][j] = min_{S_i – l_i \leq k < S_i}\{dp[i-1][k]-profit_i*k\}+profit_i*j\]

我们发现，这样的话整个方程在\(i\)的循环之下，算是只跟变量\(k\)扯上关系了。我们会发现，只要有\(k_1<k_2\)且\(dp[i-1][k_1]-profit_i*k_1<dp[i-1][k_2]-profit_i*k_2\)，那么就可以直接排除掉答案\(k_1\)。那么就可以使用单调队列来做到这一点。

下面是核心的 DP 代码：

int calc(int i, int k)
{
    return dp[i - 1][k] - wks[i].p * k;
}

// in ( int main() )
for (int i = 1; i <= k; i++)
{
    deque<int> q;
    for (int j = max(0, wks[i].s - wks[i].l); j <= wks[i].s - 1; j++)
    {
        while (!q.empty() && calc(i, q.back()) <= calc(i, j))
            q.pop_back();
        q.push_back(j);
    }
    for (int j = 1; j <= n; j++)
    {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        if (j >= wks[i].s)
        {
            while (!q.empty() && q.front() < j - wks[i].l)
                q.pop_front();
            if (!q.empty())
                dp[i][j] = max(dp[i][j], calc(i, q.front()) + wks[i].p * j);
        }
    }
}

In Conclusion

整个单调队列优化会为后面的斜率优化做基础（因为我学这个单调队列优化就是有一道题要求使用斜率优化），所以请务必搞懂这个操作。