AT [ABC176F] Brave CHAIN

首先可以发现这样一个事实：在每次操作当中，都有三张牌是已经固定的，只有两张牌是不确定的，于是我们可以发下每一次操作的状态可以简单的使用这两张牌来描述，于是可以考虑令 \(dp_{i, j, k}\) 表示当前进行到第 \(i\) 轮操作，当前剩下来的两张牌分别为 \(j, k\) 的最大得分。直接转移是 \(O(\binom{5}{3} = 10)\) 的，因此总复杂度是 \(O(n ^ 3 \times 10)\) 的。还需要进一步优化这个 \(dp\)，但是貌似这个状态是不能压缩的，于是可以考虑一下转移的过程。因为有三张牌是已经确定的，可以发现这样一个事实，如果留下来的两张牌都不是这确定的三张牌，那么转移的过程相当于将上一轮的 \(dp\) 值继承过来再整体加上一个数，我们直接使用上一轮的 \(dp\) 值并记录总体增量就能将这一部分的复杂度做到 \(O(1)\)；那么如果留下来的牌中至少有一张是已经确定的，那么实际上需要修改的 \(dp\) 状态也只有 \(O(n)\) 个，于是这个优化转移的想法看起来是很可行的。下面来具体讨论一下。（下面令 \(dp\) 为当前轮的 \(dp\) 值，\(L\) 为上一轮的 \(dp\) 值）

我们令之前继承过来的两张牌为 \(x, y\) 已经固定的牌为 \(A, B, C\)。假如删掉的牌为 \(A, B, C\)，如果 \(A, B, C\) 不完全相等，那么就会有转移 \(dp_{x, y} = L_{x, y}\)，相当于没有变，不需要修改，保证每次开始时 \(dp = L\) 即可；如果 \(A = B = C\)，就有转移 \(dp_{x, y} = L_{x, y} + 1\) 相当于将所有位置整体加 \(1\)，但会有这样一个问题，当前的一些状态可能是不合法的，但之后可能合法，它也需要加上之前的增加量，这样看来似乎我们不得不每次修改都全体加 \(1\)，但实际上这是不必要的。仔细想想，如果 \(A = B = C\) 我们为什么不直接再最开始就删去直接对所有贡献 \(+1\) 呢，于是我们事先处理好 \(A = B = C\) 的情况并将这种情况删去即可。

接下来是 \(x, y\) 中一个带上 \(A, B, C\) 中的两个删去的转移。以带 \(A, B\) 为例就会有：

\[dp_{C, x} = \max\limits_{i = 1} ^ n\{L_{x, i}\}
\]

直接对于每一行维护 \(S_x = \max\limits_{i = 1} ^ n dp_{x, i}\) 即可。特别的如果 \(A = B\)，那么还有转移 \(dp_{C, x} = L_{A, x} + 1\)。

最后是 \(x, y\) 都会被删去的情况，以 \(A, B\) 留下为例，会有转移：

\[dp_{A, B} = \max\{\max\limits_{i = 1, j = 1} ^ n L_{i, j}, L_{C, C} + 1\}
\]

于是只需要维护全局最大值 \(Max\) 即可。最后我们需要将 \(L, S, Max\) 修改，直接在上述转移时记录修改了那些位置最后直接暴力修改即可。

#include<bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for(int i = l; i <= r; ++i)

const int N = 2000 + 5;

const int M = 20000 + 5;

const int inf = 1000000000;

struct Modify{

    int x, y;

}up[M];

int n, m, ans, Max, a[N * 3], b[N], f[N], S[N], L[N][N], dp[N][N];

int read(){

    char c; int x = 0, f = 1;

    c = getchar();

    while(c > '9' || c < '0'){ if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

int chkmax(int &a, int b){

    return a = max(a, b);

}

int main(){

    n = read();

    rep(i, 1, n * 3) a[i] = read();

    rep(i, 1, n - 1){

        int Fi = 2 + (i - 1) * 3;

        if((a[Fi + 1] == a[Fi + 2]) && (a[Fi + 2] == a[Fi + 3])) ++ans, f[i] = 1;

    }

    rep(i, 1, n) rep(j, 1, n) dp[i][j] = L[i][j] = S[i] = -inf;

    L[a[1]][a[2]] = L[a[2]][a[1]] = dp[a[1]][a[2]] = dp[a[2]][a[1]] = S[a[1]] = S[a[2]] = 0;

    rep(i, 1, n - 1){

        if(f[i]) continue;

        int Fi = 2 + (i - 1) * 3; m = 0;

        dp[a[Fi + 2]][a[Fi + 1]] = chkmax(dp[a[Fi + 1]][a[Fi + 2]], max(Max, L[a[Fi + 3]][a[Fi + 3]] + 1));

        dp[a[Fi + 3]][a[Fi + 1]] = chkmax(dp[a[Fi + 1]][a[Fi + 3]], max(Max, L[a[Fi + 2]][a[Fi + 2]] + 1));

        dp[a[Fi + 3]][a[Fi + 2]] = chkmax(dp[a[Fi + 2]][a[Fi + 3]], max(Max, L[a[Fi + 1]][a[Fi + 1]] + 1));

        up[++m].x = a[Fi + 1], up[m].y = a[Fi + 2];

        up[++m].x = a[Fi + 1], up[m].y = a[Fi + 3];

        up[++m].x = a[Fi + 2], up[m].y = a[Fi + 3];

        int A, B, C; b[1] = a[Fi + 1], b[2] = a[Fi + 2], b[3] = a[Fi + 3];

        sort(b + 1, b + 3 + 1), A = b[1], B = b[2], C = b[3];

        if(B == C) swap(A, C);

        rep(j, 1, n) if(S[j] >= 0){

            up[++m].x = j, up[m].y = A, up[++m].x = j, up[m].y = B, up[++m].x = j, up[m].y = C;

            dp[A][j] = chkmax(dp[j][A], S[j]);

            dp[B][j] = chkmax(dp[j][B], S[j]);

            dp[C][j] = chkmax(dp[j][C], S[j]);

        }

        if(A == B){

            rep(j, 1, n) if(L[j][A] >= 0){

                up[++m].x = j, up[m].y = C;

                dp[j][C] = chkmax(dp[C][j], L[j][A] + 1);

            }

        }

        rep(j, 1, m){

            int x = up[j].x, y = up[j].y;

            L[x][y] = L[y][x] = dp[x][y];

            Max = max(Max, dp[x][y]), S[x] = max(S[x], dp[x][y]), S[y] = max(S[y], dp[x][y]);

        }

    }

    printf("%d", max(Max, dp[a[n * 3]][a[n * 3]] + 1) + ans);

    return 0;

}

巴特西

AT [ABC176F] Brave CHAIN

最新文章

热门文章