[R79E]这是一道01串题5 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的二进制字符串 $S$。字符串中的每个字符均为 0 或 1。

你可以进行若干次操作。每次操作按以下步骤进行：

1. 选择并删除当前字符串最左端或最右端的一个字符；
2. 如果被删除的字符是 1，则将剩余字符串中的所有字符翻转，即把每个 0 变为 1，把每个 1 变为 0；如果被删除的字符是 0，则不进行翻转。

你可以随时停止操作。请问，至少需要进行多少次操作，才能使剩余字符串中的所有字符均为 0？

特别地，空字符串也视为满足条件。如果初始字符串中的所有字符均为 0，则可以不进行任何操作。

格式

输入格式

第一行包含一个整数 $n$，表示字符串 $S$ 的长度。

第二行包含一个长度为 $n$ 的二进制字符串 $S$。

输出格式

输出一行，包含一个整数，表示使剩余字符串中的所有字符均为 0 所需的最少操作次数。

样例

样例输入 #1

3
110

样例输出 #1

2

样例解释 #1

先删除最右端的 0，此时字符串变为 11；再删除最左端的 1，并将剩余的 1 翻转为 0。两次操作后，剩余字符串为 0。

进行至多一次操作无法使剩余字符串中的所有字符均为 0，因此答案为 $2$。

样例输入 #2

3
101

样例输出 #2

3

样例解释 #2

无论前两次操作分别删除哪一端的字符，操作后剩余的唯一字符都是 1，因此至少需要三次操作。删除全部字符后得到空字符串，满足条件。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$
$1$	$20$	$20$
$2$	$30$	$5000$
$3$	$50$	$200000$

对于 $100\%$ 的数据，$1\le n\le 200000$，$S$ 的长度为 $n$，且 $S$ 中的每个字符均为 0 或 1。