2000ms

Difficulty: 4

所属公司 : 美团

时间 :2023年8月19日

算法与标签>思维

会员专享

请先登录，开通会员或购买该题目所属题库（美团机考编程题库），可解锁完整内容。

购买题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（美团机考编程题库），可解锁完整内容。

购买题库开通会员

思路：思维 + 枚举

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

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

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

代码

题目内容

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

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