枚举一个区间 [i,j] ,判断这个区间是操作为 01010⋯ 还是 10101⋯ 拥有更小代价。
累加所有区间的最小代价即可。
时间复杂度:O(n2)
给定一个仅由 0 和 1 组成的字符串 s。一次操作可以选择一个位置,将该位置上的字符翻转:0 变为 1,1 变为 0。
如果一个字符串的任意两个相邻字符都不相同,则称该字符串是交替的。对于一个连续子串,将其变为交替串所需的最少操作次数称为该子串的代价。
请你计算 s 的所有连续子串的代价之和。
字符串 s 的长度不超过 2000。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册