101 to 010
题意翻译
最简题意:
有一个$01$序列,每次可以选出一个$101$,使其变成$010$,问最优策略下能操作几次?
$N<=500000$
输入格式:
第一行一个$n$,
后面一行为一个长度为$n$的$01$序列
感谢@SD_le 提供翻译
题目描述
[problemUrl]: https://atcoder.jp/contests/code-festival-2017-qualb/tasks/code_festival_2017_qualb_d
$ N $ 個のセルが一列に並んでいます。 何個かのセルはトークンを含んでいるかもしれません。 あなたは、 `0` と `1` からなる文字列 $ s $ が与えられます。 $ s $ の $ i $ 文字目が `1` のとき、(左から) $ i $ 番目のセルはトークンを一個含んでいます。 そうでないとき、トークンを含んでいません。
すぬけ君は、以下の操作をできる限り行いたいです。 各操作では、三個の連続するセルを選びます。 セルを左から $ X,\ Y,\ Z $ とします。 操作を行うためには、 $ X $ と $ Z $ の両方がトークンを含み、 $ Y $ はトークンを含んでいてはなりません。 次に、すぬけ君はこれらの二個のトークンを取り除き、新しいトークンを $ Y $ に一個置きます。
最適な操作の方法をしたとき、すぬけ君は何回操作を行えますか?
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ s $
输出格式
答えを出力せよ。
输入输出样例
输入样例 #1
7
1010101
输出样例 #1
2
输入样例 #2
50
10101000010011011110001001111110000101010111100110
输出样例 #2
10
说明
### 制約
- $ 1\ \leq\ N\ \leq\ 500,000 $
- $ |s|\ =\ N $
- $ s $ の各文字は `0` または `1` である。
### Sample Explanation 1
例えば、以下の方法で操作を二回行うことができます: - 最後の三個のセルに対し操作を行う。 トークンを表す文字列は `1010010` となる。 - 最初の三個のセルに対し操作を行う。 トークンを表す文字列は `0100010` となる。 操作の順番が重要であることに注意してください。 たとえば、最初に中央の三個のセルを選ぶと、それ以上操作を行えなくなります。