鏈接：https://codeforces.com/contest/934/problem/C
思路：跟多校有個(gè)題很像，但是是簡化版，還是可以采取多校那個(gè)題的做法，不過這里可以更簡單一點(diǎn)，我們考慮所有的情況，都不可能比與1212的最長公共子序列（可重復(fù)匹配）的結(jié)果更優(yōu)（自行證明），所以分析可得我們最后要求的就是與1212可重復(fù)匹配的最長公共子序列。
再說一下多校那個(gè)題，也是同樣的思路，構(gòu)造一個(gè)0123456789模式串，從中枚舉交換的位置，然后與原串進(jìn)行同樣的最長公共子序列計(jì)算（注意因?yàn)橛兄貜?fù)匹配所以交換的時(shí)候要保留左端點(diǎn)和有端點(diǎn)，如交換2和7得到的串應(yīng)該為012765432789），然后再進(jìn)行求解最長公共子序列即可。
代碼：

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]);
}
}