本文主要是介绍EOJ 3367. 咸鱼翻身，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
3367. 咸鱼翻身
Time limit per test: 2.0 seconds
Memory limit: 256 megabytes
海边躺着一排咸鱼，一些有梦想的咸鱼成功翻身（然而没有什么卵用），一些则是继续当咸鱼。大佬 kblack 想要帮这些咸鱼翻身，但是他比较懒，所以只会从某只咸鱼开始，往一个方向，一只只咸鱼翻过去，翻转若干只后就转身离去，深藏功与名，但是很不幸，kblack 的一通操作，也很可能让一些原本拥有梦想的咸鱼失去梦想。
更准确地说，kblack 会选择一个区间 [L,R] ，改变区间内所有咸鱼原本的状态。注意至少翻转一条咸鱼。
kblack 离开后想知道如果他采取最优策略，最多有多少条咸鱼成功翻身。
Input
一个整数 n (1≤n≤105) 。
接下来一行 n 个整数， 0 表示没有翻身， 1 表示处于翻身状态，数据保证只有 0 和 1 。
Output
在大佬 kblack 的操作后，最多有多少咸鱼拥有梦想（即 1 的最大数量）。
Examples
input
6 0 0 0 1 1 1
output
6
input
6 0 1 1 0 0 0
output
5
Source
2017.9.27 ACM 选拔赛
#include<bits/stdc++.h>
const int N = 1e5+10;
int a[N];
using namespace std;
int main()
{int n;cin>>n;int cnt=0;for(int i=0; i<n; i++){scanf("%d",&a[i]);if(a[i])cnt++;}if(cnt==n)cout<<n-1<<endl;else{int maxhere=0,maxnum=0;for(int i=0;i<n;i++){if(a[i])maxhere--;else maxhere++;if(maxhere<0)maxhere=0;maxnum=max(maxhere,maxnum);}cout<<maxnum+cnt<<endl;}return 0;
}
这篇关于EOJ 3367. 咸鱼翻身的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
