思路：思维 + 枚举

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

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

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

代码

题目内容

小美有一个 $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 次操作