题目:给你一串由0或1组成的串,每次可以将101转换成010,求最大的可转换次数。

题解:假设只有一个101那么只操作一次,但是会出现这种情况,比如1101、1011,像这些情况,第一个101转换成010之后会对接下来的字符串提供一个贡献。设一个长度为n的字符串由k个连续的1接一个0再接1个1(或者是一个1接一个0再接k个1),那么这种情况下这个串的可操作次数是k。但是对于11110111111这种情况我们是不好判断101作为开头还是作为结尾的,所以我们考虑两种情况:

考虑当前101作为末端(即为111....101),那么在这101之前所有的1都为其提供贡献,则有:

dp[i]=max(dp[i], dp[j-1]+i-j-1);

考虑上一个101作为首端(即为101....111),那么在这101之后所有的1都为其提供贡献,则有:

dp[i]=max(dp[i], dp[pre-3]+i-pre+1);


代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn=500005;
int n, pre;
char s[maxn];
int dp[maxn];
int main()
{
    while(~scanf("%d%s", &n, s+1)){
        memset(dp, 0, sizeof(dp));
        for(int i=3;i<=n;i++){
            dp[i]=dp[i-1];
            if(s[i]=='0')pre=0;
            if(s[i]=='1'&&s[i-1]=='0'&&s[i-2]=='1'){
                int j=i-2;
                while(s[j]=='1'&&j){
                    dp[i]=max(dp[i], dp[j-1]+i-j-1);    //当前101作为末端
                    j--;
                }
                pre=i;
            }
            if(s[i]=='1'&&pre){
                dp[i]=max(dp[i], dp[pre-3]+i-pre+1);    //上一个101作为前端
            }
        }
        printf("%d\n", dp[n]);
    }
return 0;
}