题解 | #小美的01串翻转#

思路

• 01 串相邻字符都不相等只有两种情况：
  1. 以0开头：010101....
  2. 以1开头：101010....
• 因此可以遍历字符串S的所有连续子串，模拟子串变换到情况1和情况2的操作次数，取两者中的最小值，就是该字串的权值。
• 保存操作次数， 保存操作次数，权值为。 更新为保存s[i, j + 1] -> 010101...操作次数, 为保存s[i, j + 1] -> 101010...操作次数，求得s[i, j + 1]的权值

代码

import (
    "fmt"
)
const N = 2010
var s string

func min(a, b int) int {
    if(a > b) {
        return b
    }
    return a
}

func main() {
    fmt.Scan(&s)
    n := len(s)
    var ans int

    for i := 0; i < n; i++ {
        var t1, t2 int
        for j := i; j < n; j++ {
            if(j % 2 == 0) {
                if(s[j] != '0') {
                    t1++
                } else {
                    t2++
                }
            } else {
                if(s[j] != '1') {
                    t1++
                } else {
                    t2++
                }
            }

            ans += min(t1, t2);  // s[i, j]的权值
        }
    }
    
    fmt.Print(ans)
}