题目：糟糕的打谱员

题意：给出一个长度为n（\(3 \leq n \leq 10^5\)）的谱子，第\(i\)个谱子记录有两个数：\(c_i\)代表下这步棋的人为0或1（黑方白方），\(a_i\)代表此步棋下在某个地方的编号，此时需要计算出一个最长子序列的长度，满足相邻的两个数\(c_i \neq c_{i-1} \& a_i \neq a_{i - 1}\)。

解析：首先类似于最长上升子序列，会相当O(n^2)的DP算法，但是此题可以用空间进行优化，通过一个二维数组\(pos_{c,j}(0 \leq c \leq 1,1 \leq j \leq 10)\) 表示在第i个数之前作为黑方或白方最后一步在编号\(j\)可得到的最长序列长度的位置（原谱子中的位置），通过\(c \oplus 1\)可以将黑方变成黑方。

• 状态转移方程: \(f[i] = max(f[i], f[pos[c[i]\oplus1][j]] + 1)\) （与第i步棋手相反棋手在编号\(j\)得到的最长序列 + 上第i步棋（其实就是1））。
• ps：若下的棋以编号j结尾的c[i]玩家最长序列值大于之前的序列长度值，则位置信息需要进行更新。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N  = 1e5 + 5;
int T;
int n;
int c[N], a[N], pos[5][15];
int f[N]; //到第i个位置可得到的最长的合法行棋子序列

int main()
{
    cin >> T;
    while(T --)
    {
        cin >> n;
        memset(f, 0, sizeof f);
        int res = 0;
        for(int i = 1; i <= n; i++)
            cin >> c[i] >> a[i];
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= 10; j++)
            {
                if(a[i] == j) continue; //相邻两个位置的编号不能相同
                f[i] = max(f[i], f[pos[c[i]^1][j]] + 1); //相邻两个位置玩家不能相同
            }
            if(f[i] > f[pos[c[i]][a[i]]]) pos[c[i]][a[i]] = i; //若以j结尾的c[i]玩家最长序列值改变, 则更新位置信息
            res = max(res, f[i]);
        }
        cout << res << endl;
    }
    return 0;
}