4232 - 翻转(reverse)

题目描述

小 C 有一个长度为 n01S

小 C 定义一次操作是选择串 S 的一个后缀将其 01 翻转(0 变成 11 变成 0)。

小 C 想要知道最少需要几次操作可以使得串 S 单调不降(即不存在 1\le i\lt j\le n,满足 S_i=1S_j=0)。

输入

输入的第一行包含一个整数 n

接下来一行包含长度为 n01 串,表示串 S

输出

输出共一行,包含一个整数,表示最小操作次数。

样例

输入

3
101

输出

2

输入

7
0101010

输出

5
说明

数据规模与约定

  • 对于 30\% 的数据,保证 n\le 20

  • 对于 60\% 的数据,保证 n\le 100

  • 对于 100\% 的数据,保证 1\le n\le 10^5

样例 1 解释

第一次操作:对整个串进行翻转,串 S 变为 010

第二次操作:翻转后缀 [3,3],串 S 变为 011

可以证明不存在操作次数更小的解,当然可能存在其他操作次数为 2 的操作方案。

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 3 枚
难度 基础


上一题 下一题