携程0905笔试第二题

看解答都是三维dp
好像二维dp也能做
dp[i][j]表示子串s[i...j]全变为1的最小操作数
public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String s = in.next();
        char[] cs = s.toCharArray();

        int res = 0;

        int[][] dp = new int[n][n];
        for(int i = 0; i < n; i++){
            dp[i][i] = cs[i] == '0' ? 1 : 0;
            res += cs[i] == '0' ? 1 : 0;
        }

        for (int i = n - 1; i >= 0; i--) {
            for(int j = i + 1; j < n; j++){
                if(cs[j] == '1'){
                    dp[i][j] = dp[i][j - 1];
                }else{
                    if(cs[j - 1] == '0'){
                        dp[i][j] = dp[i][j - 1];
                    }else{
                        dp[i][j] = dp[i][j - 1] + 2;
                    }
                }

                if((j - i + 1) % 2 != 0 &amp;&amp; dp[i][j] % 2 != 0){
                    res ++;
                }
            }
        }
        System.out.println(res);
    }