网站建设的公司,这两天发生的重大新闻,建站网站关键词优化,一站式装修的利弊Problem 2253 Salty Fish Accept: 35 Submit: 121Time Limit: 1000 mSec Memory Limit : 32768 KB Problem Description 海边躺着一排咸鱼#xff0c;一些有梦想的咸鱼成功翻身#xff08;然而没有什么卵用#xff09;#xff0c;一些则是继续当咸鱼。一个善良的渔夫… Problem 2253 Salty Fish Accept: 35 Submit: 121Time Limit: 1000 mSec Memory Limit : 32768 KB Problem Description 海边躺着一排咸鱼一些有梦想的咸鱼成功翻身然而没有什么卵用一些则是继续当咸鱼。一个善良的渔夫想要帮这些咸鱼翻身但是渔夫比较懒所以只会从某只咸鱼开始往一个方向一只只咸鱼翻过去翻转若干只后就转身离去深藏功与名。更准确地说渔夫会选择一个区间[L,R]改变区间内所有咸鱼的状态至少翻转一只咸鱼。 渔夫离开后想知道如果他采取最优策略最多有多少只咸鱼成功翻身但是咸鱼大概有十万条所以这个问题就交给你了 Input 包含多组测试数据。 每组测试数据的第一行为正整数n表示咸鱼的数量。 第二行为长n的01串0表示没有翻身1表示成功翻身。 n≤100000 Output 在渔夫的操作后成功翻身咸鱼即1的最大数量。 Sample Input 5 1 0 0 1 0 3 0 1 0 Sample Output 4 2 Hint 对于第一个样例翻转区间[2,3]序列变为1 1 1 1 0。 对于第二个样例翻转整个区间序列变为1 0 1。 思路最大连续子区间和问题考虑两部分第一记录好原本的序列中1的个数sum1 第二现在要反转一个区间此时对原串修改0的部分改成11的部分改成-1因为每次反转原本没翻身的鱼翻身了则翻身的鱼个数1而原本翻身的鱼又变回咸鱼翻身鱼个数-1对修改后的串求最大连续子区间和sum2,sum1sum2即是最优解。当然本题需要注意如果所有鱼本来都是1的状态则至少需要翻转一条最佳方案则为n-1. AC代码 #define _CRT_SECURE_NO_DEPRECATE
#includeiostream
#includeset
#includevector
#includealgorithm
#includecstring
using namespace std;
const int N_MAX 10000050;
int fish[N_MAX],a[N_MAX];
int n;
int main() {while (scanf(%d,n)!EOF) {int sum 0;for (int i 0; i n;i) {scanf(%d,fish[i]);if (fish[i]) { sum fish[i], a[i] -1; }else a[i] 1;}int sum2 0,max_suma[0];for (int i 0; i n;i) {if(sum20)sum2 a[i];else sum2 a[i];max_sum max(max_sum, sum2);}printf(%d\n,max_sumsum);}return 0;
} 转载于:https://www.cnblogs.com/ZefengYao/p/7192290.html
