Codeforces 327A-Flipping Game(暴力枚举)
Iahub got bored, so he invented a game to be played on paper.
He writes n integers a1, a2, ..., an. Each of those integers can be either 0 or 1. He's allowed to do exactly one move: he chooses two indices i and j (1 ≤ i ≤ j ≤ n) and flips all values ak for which their positions are in range [i, j] (that is i ≤ k ≤ j). Flip the value of xmeans to apply operation x = 1 - x.
The goal of the game is that after exactly one move to obtain the maximum number of ones. Write a program to solve the little game of Iahub.
The first line of the input contains an integer n (1 ≤ n ≤ 100). In the second line of the input there are n integers: a1, a2, ..., an. It is guaranteed that each of those n values is either 0 or 1.
Print an integer — the maximal number of 1s that can be obtained after exactly one move.
5 1 0 0 1 0
4
4 1 0 0 1
4
题意:翻牌游戏。给出n张牌,每张牌仅仅有0和1两种状态。给出初始状态。对于翻牌操作这样规定:每次操作可将区间[i,j](1=<i<=j<=n)内牌的状态翻转(即0变1,1变0)。求一次翻转操作后,1的个数尽量多。
枚举区间+遍历区间推断,O(n^3);
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <cctype> #include <cstdlib> #include <set> #include <map> #include <vector> #include <string> #include <queue> #include <stack> #include <cmath> using namespace std; const int INF=0x3f3f3f3f; #define LL long long int a[110]; int main() { int n,num[2]; while(~scanf("%d",&n)) { int ans=0; for(int i=0;i<n;i++) { scanf("%d",a+i); if(a[i]==1) ans++; } int pos=ans; if(pos==n) { printf("%d\n",n-1); continue; } for(int i=0;i<n;i++) for(int j=i;j<n;j++) { memset(num,0,sizeof(num)); for(int k=i;k<=j;k++) num[a[k]]++; if(num[0]>num[1]) ans=max(ans,pos+num[0]-num[1]); } printf("%d\n",ans); } return 0; }
相关文章
- 【Educational Codeforces Round 101 (Rated for Div. 2) C】Building a Fence
- 【Codeforces 977F】Consecutive Subsequence
- 【Codeforces 342A】Xenia and Divisors
- 【22.70%】【codeforces 591C】 Median Smoothing
- 【codeforces 766B】Mahmoud and a Triangle
- 【codeforces 761C】Dasha and Password(贪心+枚举做法)
- 【codeforces 758B】Blown Garland
- 【codeforces 792C】Divide by Three
- 【codeforces 803F】Coprime Subsequences
- Codeforces Round #273 (Div. 2)
- Educational Codeforces Round 27