选拔赛第一场（翻转游戏）（Codeforces Round #4

链接：https://codeforces.com/contest/934/problem/C
思路：跟多校有个题很像，但是是简化版，还是可以采取多校那个题的做法，不过这里可以更简单一点，我们考虑所有的情况，都不可能比与1212的最长公共子序列（可重复匹配）的结果更优（自行证明），所以分析可得我们最后要求的就是与1212可重复匹配的最长公共子序列。
再说一下多校那个题，也是同样的思路，构造一个0123456789模式串，从中枚举交换的位置，然后与原串进行同样的最长公共子序列计算（注意因为有重复匹配所以交换的时候要保留左端点和有端点，如交换2和7得到的串应该为012765432789），然后再进行求解最长公共子序列即可。
代码：

import java.util.Arrays;
import java.util.Scanner;

public class atwistymovement {
    
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int dp[][] = new int[n+1][4];
        int a[] = new int[n+1];
        for(int i=0;i<=n;i++)
        Arrays.fill(dp[i], 0);
        for(int i=1;i<=n;i++)a[i] = scan.nextInt();
        for(int i=1;i<=n;i++) {
            for(int j=0;j<4;j++) {
                if(j>0)dp[i][j] = dp[i][j-1];
                else dp[i][j] = 0;
                int t = 0;
                if(j==0||j==2) {
                    if(a[i]==1)t = 1;
                    else t = 0;
                }
                else {
                    if(a[i]==2)t = 1;
                    else t = 0;
                }
                dp[i][j] = Math.max(dp[i][j], dp[i-1][j]+t);
    }
        }
        System.out.println(dp[n][3]);
}
}