AT_abc176_f

cosf · 2024-10-04 11:22:29 · 题解

考虑一个朴素的 dp。

令 dp_{i, a, b} 表示处理到第 3i - 2 位，其中第一位为 a，第二位为 b 的最大答案。初始时 dp_{1, v_1, v_2} = 0，其他为 -\infty。

转移时，我们需要第三到五的数 c, d, e，它们当前的排列方式是：a, b, c, d, e, \dots。

显然，这个式子与 a, b 顺序无关，即总有 dp_{i, a, b} = dp_{i, b, a}。

则我们可以有三个式子，其最左侧的 = 都是取 \max。

则答案为 dp_{n, a, b} + [a = b = v_{3n}]。

根据 dp_{i, a, b} 转移到的状态只有 O(5^2) 种，这种朴素递推的时间复杂度为 O(n^3)，当然过不了。

这个式子可以优化。

对于第一个式子，如果我们想要 [a = b = e] = 1，则 a, b 的值唯一确定，而 c, d 的值也是确定的，故此种转移的复杂度是 O(1) 的。如果不需要 [a = b = e] = 1，则 a, b 可以为任意值，直接取全局 \max 即可。

对于第二个式子，因为 [c = d = e] 的值和 a, b 无关，所以直接全局加法即可。

对于第三个式子，如果 [b = c = d] = 1，则需要修改的 dp 值只有 dp_{i, a, e} = dp_{i, a, c} + 1，只有一个变量在改变，复杂度 O(n)。如果不需 [b = c = d] = 1，则右侧相当于求 dp_{i - 1, a, b} 在 b 变化的 \max，因此维护一下行的 \max 即可，时间复杂度仍为 O(n)。

这样对于一个 i 我们所需的复杂度为 O(n)，则总复杂度为 O(n^2)，可以通过。

具体实现可以开一个 queue 或者 stack 来保存每次的操作，等每个操作都处理完再统一复制到原来的 dp 数组上。这样可以节省空间，也十分好写。

#include <iostream>
#include <cstring>
#include <queue>
#include <array>
using namespace std;

#define MAXN 3005

using tii = array<int, 3>;

int dp[MAXN][MAXN], ps = 0;

int n;

int v[MAXN * 3];

int main()
{
    cin >> n;
    for (int i = 1; i <= 3 * n; i++)
    {
        cin >> v[i];
    }
    memset(dp, -0x3f, sizeof(dp));
    dp[v[1]][v[2]] = dp[v[2]][v[1]] = // dp[i][a][0] 表示第 a 行的 max
    dp[v[1]][0] = dp[v[2]][0] = // dp[i][0][0] 表示全局 max
    dp[0][0] = 0;
    queue<tii> q;
    for (int i = 2; i <= n; i++)
    {
        int c = v[i * 3 - 3], d = v[i * 3 - 2], e = v[i * 3 - 1], cp = 0;
        // dp[i][c][d]
        q.push({c, d, dp[e][e] + 1});
        q.push({c, d, dp[0][0]});
        q.push({d, e, dp[c][c] + 1});
        q.push({d, e, dp[0][0]});
        q.push({e, c, dp[d][d] + 1});
        q.push({e, c, dp[0][0]});
        // dp[i][a][b]
        if (c == d && d == e)
        {
            cp++;
            ps++;
        }
        // dp[i][a][e]
        for (int a = 1; a <= n; a++)
        {
            if (c == d)
            {
                q.push({a, e, dp[a][c] + 1});
            }
            q.push({a, e, dp[a][0]});
            if (d == e)
            {
                q.push({a, c, dp[a][d] + 1});
            }
            q.push({a, c, dp[a][0]});
            if (e == c)
            {
                q.push({a, d, dp[a][e] + 1});
            }
            q.push({a, d, dp[a][0]});
        }
        // postprocessing
        while (!q.empty())
        {
            auto [a, b, w] = q.front();
            q.pop();
            w -= cp; // 不减就相当于全局加之后再转移，答案会错。
            dp[a][b] = dp[b][a] = max(dp[a][b], w);
            dp[a][0] = max(dp[a][0], w);
            dp[b][0] = max(dp[b][0], w);
            dp[0][0] = max(dp[0][0], w);
        }
    }
    int res = 0;
    for (int a = 1; a <= n; a++)
    {
        for (int b = a; b <= n; b++)
        {
            res = max(res, dp[a][b] + (a == b && a == v[3 * n]));
        }
    }
    cout << res + ps << endl;
    return 0;
}