ABC F题选讲

选一些比较有意思的ABC F题

F - Brave CHAIN

转换原题意：初始有\(2\)张牌，每次操作拿\(3\)张牌并从\(5\)张牌中丢弃\(3\)张，如果\(3\)张一样得分\(+1\)

进行\(dp\)

step 1

设\(f_{i,j,k}\)表示进行\(i\)轮游戏后，手里剩下的牌为\(i\)和\(j\)时的最大值

枚举\(i,j,k\)和这轮游戏后手中的牌，复杂度\(O(n^5)\)

step 2

如果当前手中的牌为\(j,k\)，每一轮新拿的三张牌是确定的，一轮过后的\(2\)张牌只能从\(5\)张中选，共\(10\)种情况，复杂度\(O(10\times n^3)\)

step 3

可以按照\(2\)张牌有几张来自新拿的\(3\)张进行分类加速转移

1、如果\(2\)张都来自新拿的，则可以从之前的任意状态进行转移，记录最大值即可。还要考虑丢弃的\(3\)张牌相同的情况分数\(+1\)

2、如果有\(1\)张牌来自新拿的，另一张牌为\(x\)，说明\(x\)来自之前的牌，则必须从有\(x\)的状态进行转移（还是记录最大值）。同样特殊考虑\(3\)张牌相同进行额外转移

3、如果\(j,k\)均不来自新拿的，则丢弃的三张牌一定是新拿的，判断一下是否有分。从上一步的\(j,k\)转移

观察发现，每次转移情况\(1\)的复杂度是常数，\(2\)的复杂度为\(O(n)\)，但存在情况\(3\)，复杂度并没有得到提高

但\(3\)的所有转移形式一致，不用暴力算，用一个变量记录加的分就好了。但如果选择情况\(1，2\)就不能获得\(3\)的加分，在转移的时候减去即可

#include <bits/stdc++.h>
using namespace std;
void read (int &x) {
    char ch = getchar(); x = 0;
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
} const int N = 2010;
int n, m, mx, tot, mm[N], a[N * 3], f[N][N], p[3], mt[N], qwq[N][N];
#define Max(a, b) (a = a >= b ? a : b)
signed main() {
    read (n); m = 3 * n;
    for (int i = 1; i <= m; ++i) read (a[i]);
    memset (f, 0xcf, sizeof (f));
    f[a[1]][a[2]] = f[a[2]][a[1]] = 0;
    memset (mm, 0xcf, sizeof (mm));
    mm[a[1]] = mm[a[2]] = 0;
    for (int t = 1; t < n; ++t) {
        // memset (f[k], 0xcf, sizeof (f[k]));
        memset (mt, 0xcf, sizeof (mt));
        p[0] = a[t * 3], p[1] = a[t * 3 + 1], p[2] = a[t * 3 + 2];
        int num = (p[0] == p[1] && p[1] == p[2]), tmp = 0; tot += num;
        // 记录有用的值
        for (int i = 0, x, y; i < 3; ++i)
            for (int j = 1; j <= n; ++j) {
                if (i == 0) x = 1, y = 2;
                if (i == 1) x = 0, y = 2;
                if (i == 2) x = 0, y = 1;
                if (p[x] == p[y]) qwq[j][p[x]] = f[j][p[x]];
            }
        for (int i = 0; i < 3; ++i)
            for (int j = i + 1; j < 3; ++j)
                qwq[p[3 ^ i ^ j]][p[3 ^ i ^ j]] = f[p[3 ^ i ^ j]][p[3 ^ i ^ j]];
        // 全部都是之前的直接 tot+1
        // 有一张新发
        for (int i = 0, x, y; i < 3; ++i)
            for (int j = 1; j <= n; ++j) {
                Max (f[p[i]][j], mm[j] - num);
                if (i == 0) x = 1, y = 2;
                if (i == 1) x = 0, y = 2;
                if (i == 2) x = 0, y = 1;
                if (p[x] == p[y]) Max (f[p[i]][j], qwq[j][p[x]] + 1 - num);
                Max (f[j][p[i]], f[p[i]][j]);
                Max (tmp, f[p[i]][j]);
                Max (mt[p[i]], f[p[i]][j]);
                Max (mt[j], f[p[i]][j]);
            }
        // 都在新发的三张中
        for (int i = 0; i < 3; ++i)
            for (int j = i + 1; j < 3; ++j) {
                Max (f[p[i]][p[j]], mx - num);
                Max (f[p[i]][p[j]], qwq[p[3 ^ i ^ j]][p[3 ^ i ^ j]] + 1 - num);
                Max (f[p[j]][p[i]], f[p[i]][p[j]]);
                Max (tmp, f[p[i]][p[j]]);
                Max (mt[p[i]], f[p[i]][p[j]]);
                Max (mt[p[j]], f[p[i]][p[j]]);
            }
        Max (mx, tmp); for (int i = 1; i <= n; ++i) Max (mm[i], mt[i]);
    }
    return printf ("%d\n", max (mx, f[a[m]][a[m]] + 1) + tot), 0;
}

ABC F题选讲

原文：https://www.cnblogs.com/whx666/p/13736658.html