A7167 | $雾港城的开关$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

雾港城的主干道上装着一排开关，排成一个长度为 $n$ 的 $01$ 串 $s$。$0$ 表示“关”，$1$ 表示“开”。 你可以进行若干次操作：每次选择一个位置 $i$（$1\le i\le n$），把从 $i$ 到 $n$ 的所有开关状态全部翻转（$0\leftrightarrow1$）。 你希望最后所有开关都变成 $0$。请输出最少需要多少次操作。

第一行一个整数 $n$。 第二行一个长度为 $n$ 的 $01$ 串 $s$。

输出一个整数，表示最少操作次数。

输入 #1

6
001110

输出 #1

数据范围与测试点 测试点编号$n$ 上界$1\sim4$$n\le20$$5\sim10$$n\le10000$$11\sim20$$n\le200000$ --- 样例1解释 在 $i=3$ 处翻转后串变为 000001，再在 $i=6$ 翻转一次得到全 0，共 $2$ 次；并且无法只用 $1$ 次完成，所以答案为 $2$。

C++ 编辑器

输入

输出