[AtCoder Code Festival 2017 QualB D/At3575] 101 to 010

[Atcoder Code Festival 2017 QualB/At3575] 101 to 010

有一个01序列，每次可以选出一个101，使其变成010，问最优策略下能操作几次？

考虑像 1111101 或者 1011111 这样的东西，它们最多能被操作的次数为长度-2

设(l[i]) 表示 (i) 左边第一个 (0) 的位置

设 (f[i]) 表示前缀的最大操作数

对于每个 (a[i]=1) 的位置，我们考虑进行转移

• 对于 ([i-2,i]) 为 101 的情况，

  • 对类似100 | 1111101这种，我们得到
  [f[i] leftarrow f[l[i-2]] + i-l[i-2]-2 ]
  • 对于类似 11101| 11101 这种，我们得到
  [f[i] leftarrow f[l[i-2]+1] +i-(l[i-2]+1)-2 ]

• 否则，考虑类似 1011111 这样的情况，这时 (l[i]>1, a[l[i]-1]=1)，我们得到

  [f[i] leftarrow f[l[i]-2] +i-l[i]+2-2 ]

#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;

char s[N];
int n,l[N],f[N];
int main() {
    scanf("%d%s",&n,s+1);
    for(int i=1;i<=n;i++) {
        if(s[i]=='0') l[i]=i;
        else l[i]=l[i-1];
    }
    for(int i=1;i<=n;i++) {
        f[i]=f[i-1];
        if(s[i]=='1') {
            if(s[i-2]=='1' && s[i-1]=='0')
                f[i]=max(f[i],max(f[l[i-2]]+i-l[i-2]-2,f[l[i-2]+1]+i-l[i-2]-3));
            else if(l[i]>1 && s[l[i]-1]=='1') f[i]=max(f[i],f[l[i]-2]+i-l[i]);
        }
    }
    cout<<f[n];
}