小 C 有一个长度为 n 的 01 串 S。
小 C 定义一次操作是选择串 S 的一个后缀将其 01 翻转(0 变成 1,1 变成 0)。
小 C 想要知道最少需要几次操作可以使得串 S 单调不降(即不存在 1\le i\lt j\le n,满足 S_i=1,S_j=0)。
输入的第一行包含一个整数 n。
接下来一行包含长度为 n 的 01 串,表示串 S。
输出共一行,包含一个整数,表示最小操作次数。
3 101
2
7 0101010
5
对于 30\% 的数据,保证 n\le 20。
对于 60\% 的数据,保证 n\le 100。
第一次操作:对整个串进行翻转,串 S 变为 010。
第二次操作:翻转后缀 [3,3],串 S 变为 011。
可以证明不存在操作次数更小的解,当然可能存在其他操作次数为 2 的操作方案。