题解 | 糟糕的打谱员

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
        sc.close();
    }
    
    public static void solve(Scanner sc) {
        int n = sc.nextInt();
        Pair[] a = new Pair[n + 1];
        int[] dp = new int[n + 1];
        
        // 初始化dp数组为1
        for (int i = 1; i <= n; i++) {
            dp[i] = 1;
        }
        
        // 读取输入数据
        for (int i = 1; i <= n; i++) {
            int type = sc.nextInt();
            int color = sc.nextInt();
            a[i] = new Pair(type, color);
        }
        
        // 创建11x2的二维数组，初始化为0
        int[][] t = new int[11][2];
        
        // 处理第一个元素
        dp[1] = 1;
        t[a[1].color][a[1].type] = Math.max(t[a[1].color][a[1].type], dp[1]);
        
        // 动态规划过程
        for (int i = 2; i <= n; i++) {
            int currentType = a[i].type;
            int currentColor = a[i].color;
            
            for (int j = 1; j <= 10; j++) {
                if (currentColor == j) continue;
                // 取相反类型中不同颜色的最大值
                dp[i] = Math.max(dp[i], t[j][1 - currentType] + 1);
            }
            
            // 更新t数组
            t[currentColor][currentType] = Math.max(t[currentColor][currentType], dp[i]);
        }
        
        // 找出最大值
        int maxVal = 0;
        for (int i = 1; i <= n; i++) {
            maxVal = Math.max(maxVal, dp[i]);
        }
        
        System.out.println(maxVal);
    }
    
    // 辅助类用于存储类型和颜色对
    static class Pair {
        int type;
        int color;
        
        public Pair(int type, int color) {
            this.type = type;
            this.color = color;
        }
    }
}