题解 | #糟糕的打谱员#

本题要求从一个记录序列中找出最长的子序列，满足相邻两步玩家交替且劫争编号不同。由于劫争编号范围很小（1~10），可以采用动态规划，按顺序扫描每一步，维护以每种（玩家，劫争）组合结尾的最长子序列长度。对于当前步 (c, a)，它可以接在之前任意一个与 c 不同且劫争不等于 a 的状态之后，因此只需从另一玩家的所有劫争（排除 a）中找出最大值，加 1 更新 dp[c][a]。这样保证了子序列的顺序性和合法性。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;

        vector<vector<int>> dp(2, vector<int>(11, 0));

        for (int i = 0; i < n; i++) {
            int c, a;
            cin >> c >> a;
            int opp = 1 - c;
            int best = 0;
            for (int k = 1; k <= 10; k++) {
                if (k != a)
                    best = max(best, dp[opp][k]);
            }
            int newLen = best + 1;
            dp[c][a] = max(dp[c][a], newLen);
        }

        int ans = 0;
        for (int c = 0; c < 2; c++)
            for (int a = 1; a <= 10; a++) {
                ans = max(ans, dp[c][a]);
            }
        cout << ans << endl;
    }
}

计算复杂度

• 时间复杂度：每组需遍历 n 个元素，每次遍历枚举 10 个劫争，故 O(10·n) = O(n)，总复杂度 O(T·n)。n ≤ 10⁵，T ≤ 10，总运算量约 10⁷，可轻松通过。
• 空间复杂度：仅需常数大小的 dp 数组，O(1)。