? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Problem 2253 Salty Fish

Accept: 35????Submit: 121
Time Limit: 1000 mSec????Memory Limit : 32768 KB

Problem Description

海邊躺著一排咸魚，一些有夢想的咸魚成功翻身（然而沒有什么卵用），一些則是繼續(xù)當(dāng)咸魚。一個善良的漁夫想要幫這些咸魚翻身，但是漁夫比較懶，所以只會從某只咸魚開始，往一個方向，一只只咸魚翻過去，翻轉(zhuǎn)若干只后就轉(zhuǎn)身離去，深藏功與名。更準(zhǔn)確地說，漁夫會選擇一個區(qū)間[L,R]，改變區(qū)間內(nèi)所有咸魚的狀態(tài)，至少翻轉(zhuǎn)一只咸魚。

漁夫離開后想知道如果他采取最優(yōu)策略，最多有多少只咸魚成功翻身，但是咸魚大概有十萬條，所以這個問題就交給你了！

Input

?

包含多組測試數(shù)據(jù)。

每組測試數(shù)據(jù)的第一行為正整數(shù)n，表示咸魚的數(shù)量。

第二行為長n的01串，0表示沒有翻身，1表示成功翻身。

?

n≤100000

Output

在漁夫的操作后，成功翻身咸魚（即1）的最大數(shù)量。

Sample Input

5 1 0 0 1 0 3 0 1 0

Sample Output

4 2

Hint

對于第一個樣例，翻轉(zhuǎn)區(qū)間[2,3]，序列變?yōu)? 1 1 1 0。

對于第二個樣例，翻轉(zhuǎn)整個區(qū)間，序列變?yōu)? 0 1。?

?

思路：最大連續(xù)子區(qū)間和問題，考慮兩部分，第一：記錄好原本的序列中1的個數(shù)sum1 第二：現(xiàn)在要反轉(zhuǎn)一個區(qū)間，此時對原串修改，0的部分改成1，1的部分改成-1，因為每次反轉(zhuǎn)，原本沒翻身的魚翻身了，則翻身的魚個數(shù)+1，而原本翻身的魚又變回咸魚，翻身魚個數(shù)-1，對修改后的串求最大連續(xù)子區(qū)間和sum2,sum1+sum2即是最優(yōu)解。當(dāng)然本題需要注意如果所有魚本來都是1的狀態(tài)，則至少需要翻轉(zhuǎn)一條，最佳方案則為n-1.

AC代碼：

#define _CRT_SECURE_NO_DEPRECATE #include<iostream> #include<set> #include<vector> #include<algorithm> #include<cstring> using namespace std; const int N_MAX = 100000+50; 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_sum=a[0];for (int i = 0; i < n;i++) {if(sum2>0)sum2 += a[i];else sum2 = a[i];max_sum = max(max_sum, sum2);}printf("%d\n",max_sum+sum);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/ZefengYao/p/7192290.html

總結(jié)

以上是生活随笔為你收集整理的FOJ Problem 2253 Salty Fish的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。