思路：思维 + 枚举

枚举一个区间 $[i, j]$ ，判断这个区间是操作为 $01010\cdots$ 还是 $10101\cdots$ 拥有更小权值。

累加所有区间的最小权值即可。

时间复杂度：$O(n^2)$

代码

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.length();

    int ans = 0;
    for (int i = 0; i < n; i++) {
        // s[i] ~ s[j] 的最小
        // start[0] 表示将设置为 s[i] == 0，从 s[i] 到 s[k] 为 0101 这种交替的情况的最小权值
        array<int, 2> start = {0, 0};
        for (int j = i; j < n; j++) {
            if (s[j] == '1') {
                if ((j - i) % 2 == 0) {
                    start[0]++;
                } else {
                    start[1]++;
                }
            } else {
                if ((j - i) % 2 == 1) {
                    start[0]++;
                } else {
                    start[1]++;
                }
            }

            ans += min(start[0], start[1]);
        }
    }

    cout << ans << "\n";

    return 0;
}

Python

s = input()
n = len(s)

ans = 0
for i in range(n):
    
    # s[i] ~ s[j] 的最小
    # start[0] 表示将设置为 s[i] == 0，从 s[i] 到 s[k] 为 0101 这种交替的情况的最小权值
    start = [0, 0]
    for j in range(i, n):
        if int(s[j]) == 1:
            if (j - i) % 2 == 0:
                start[0] += 1
            else:
                start[1] += 1
        else:
            if (j - i) % 2 == 1:
                start[0] += 1
            else:
                start[1] += 1
                
        ans += min(start)

print(ans)

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        int n = s.length();

        int ans = 0;
        for (int i = 0; i < n; i++) {
            // s[i] ~ s[j] 的最小
            // start[0] 表示将设置为 s[i] == 0，从 s[i] 到 s[k] 为 0101 这种交替的情况的最小权值
            int[] start = new int[2];
            for (int j = i; j < n; j++) {
                if (s.charAt(j) == '1') {
                    if ((j - i) % 2 == 0) {
                        start[0]++;
                    } else {
                        start[1]++;
                    }
                } else {
                    if ((j - i) % 2 == 1) {
                        start[0]++;
                    } else {
                        start[1]++;
                    }
                }

                ans += Math.min(start[0], start[1]);
            }
        }

        System.out.println(ans);
    }
}

题目内容

小美有一个 $01$ 串 $s$。每次操作可以将一个 $1$ 修改为 $0$ 或者一个 $0$ 修改为 $1$ 。

小美不喜欢 $01$ 串相邻字符相等，所以他要操作使得 $01$ 串任意相邻字符不相等。

对于一个 $01$ 串，其权值为使得相邻字符不相等的最少操作次数。

现在小美想问你，对于给定的 $s$ ，其所有子串的权值之和是多少。

输入描述

一行，一个 $01$ 串 $s(|s|\leq 2000)$ 。

输出描述

一个整数，表示一个 $01$ 串的所有子串的权值之和是多少。

样例

输入

000

输出

3

说明

长度为 $2$ 的子串均调整为 01 ，需要 2 次操作

长度为 $3$ 的子串调整为 010 ，需要 1 次操作

共 3 次操作