codeforces 327 A Ciel and Dancing

给你一串只有0和1的数字，然后对某一区间的数翻转1次（0变1 1变0），只翻转一次而且不能不翻转，然后让你计算最多可能出现多少个1。

这里要注意很多细节比如全为1，要求必须翻转，这时候我们只要翻转一个1就可以了，对于其他情况，我们只要计算区间里面如果0多于1，将其翻转后计算1的总数，然后取最大值。

//cf 191 A

//2013-07-04-22.13

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

int a[105];

int cnt[105];

int main()

{

    int n;

    while (scanf("%d", &n) != EOF)

    {

        int sum = 0;

        memset(cnt, 0, sizeof(cnt));

        for (int i = 1; i <= n; i++)

        {

            scanf("%d", &a[i]);

            if (a[i] == 0)

            {

                cnt[i] = cnt[i-1] + 1;

            }

            else

            {

                cnt[i] = cnt[i-1];

                sum++;

            }

        }

        if (sum == n)

        {

            printf("%d\n", sum - 1);

            continue;

        }

        if (sum == n-1)

        {

            printf("%d\n", n);

            continue;

        }

        int ans = sum + 1;

        for (int i = 2; i <= n; i++)

        {

            for (int j = 1; j < i; j++)

            {

                if ((cnt[i] - cnt[j-1]) > ((i-j+1) - (cnt[i] - cnt[j-1])))

                    ans = max (ans, sum - ((i-j+1) - (cnt[i] - cnt[j-1])) + (cnt[i] - cnt[j-1]));

            }

        }

        printf("%d\n", ans);

    }

    return 0;

}

巴特西

codeforces 327 A Ciel and Dancing

最新文章

热门文章