题解 | 小美的01串翻转

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});
function getCost(str, s, e, c) {
    let r = 0;
    for (let i = s; i <= e; i++) {
        if (i & 1 && str[i] !== c) r++;
        if (!(i & 1) && str[i] === c) r++;
    }
    return r;
}

rl.on("line", (line) => {
    const tokens = line.split(" ");
    const str = tokens[0];
    const n = str.length;
    const dp = Array.from({length: n}, () => new Array(2))
    // dp[i][0] i位置应该是0的代价
    // dp[i][1] i位置应该是1的代价
    dp[-1] = [0, 0]
    dp[0][0] = parseInt(str[0])
    dp[0][1] = (str[0] ^ 1);
    for (let i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][1] + parseInt(str[i])
        dp[i][1] = dp[i - 1][0] + (str[i] ^ 1)
    }
    let res = 0
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            // i ~ j 位置，包含i和j
            const num = (j - i + 1) % 2
            res += Math.min(
                // 当前位置是0
                // 从i到j有num个数字
                // num是奇数，i - 1位置就应该是 1
                // num是偶数，i - 1位置就应该是 0
                dp[j][0] - dp[i - 1][num],
                // 当前位置是1
                // 推论如上
                dp[j][1] - dp[i - 1][num ^ 1]
            )
        }
    }
    console.log(res)
});