糟糕的打谱员

众所周知，围棋是一项黑白双方轮流行动的棋类游戏。在围棋中，还有打劫的概念，若一方落子在某一个劫争处，则另一方不能立刻也下在这个劫争处，而之后还是可以下的。现在，你是一场史诗级围棋对弈（史诗级体现在这场棋每一步都下在了劫争上）的记谱员，但熬夜到早上七点才睡的你状态不佳，胡乱记了许多东西。

为了假装你有出色的完成记谱工作，请从你记录的谱子中找到一个最长的合法行棋子序列。

一个合法行棋子序列需要满足：

1. 任意相邻的两步，玩家不同（一黑一白）；

2. 任意相邻的两步，不能下在同一个劫争处。

子序列是指原序列中删除若干（可以不删）元素得到的新序列。

第一行是整数 $T(1\leq T\leq 10)$ ，测试组数。

每组测试用例，第一行是整数 $n(3\leq n\leq 10^5)$ ，你记录的谱子长度。

接下来 $n$ 行，每行两个数 $c_i(0\leq c_i\leq 1)$ 和 $a_i(1\leq a_i\leq 10)$ ，表示一步棋，下这步棋的人是 $c_i$ 且下在了编号为 $a_i$ 的劫争处。

#include <bits/stdc++.h> using namespace std; typedef long long ll; int n; void solve(){ scanf("%d",&n); int ans=0,f[2][12]={0}; for(int i=1;i<=n;i++){ int c,a; cin>>c>>a; for(int j=1;j<=10;j++){ if(j!=a) f[c][a]=max(f[c][a],f[1-c][j]+1); } ans=max(ans,f[c][a]); } cout<<ans<<endl; } int main(){ int t; cin>>t; while(t--){ solve(); } return 0; }

详情