文章
25
粉丝
364
获赞
68
访问
237.1k
 
思路:遇1见一,遇0加一 ,和最大子列和差不多
/*
 *  Description: 字符串区间翻转 (http://noobdream.com/DreamJudge/Issue/page/1642/)
 *  Author: 鱼翔浅底
 *  Date: 2021-02-18 22:57:14
 */
#include <cstdio>
#include <cstdlib>
using namespace std;
//翻转后得到的最多1的个数
int StringFlip(char s[], int N)
{
    int cnt = 0, max = 0, tmp = 0;
    for (int i = 0; i < N; i++)
    {
        if (s[i] == '1')
        {
            cnt++;                               //计算原来1的个数
            tmp = (tmp - 1 < 0) ? 0 : (tmp - 1); //翻转1-->0
        }
        else //翻转0-->1
        {
            tmp++;
            max = (tmp > max) ? tmp : max;
        }
    }
    return (cnt + max);
}
int main()
{
    int N;
    char s[10000000];
    while (~scanf("%d", &N))
    {
        scanf("%s", s);
        printf("%d\n", StringFlip(s, N));
    }
    return 0;
}
登录后发布评论
暂无评论,来抢沙发