[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];

}

巴特西

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

最新文章

热门文章