fzu-2253
A - Salty Fish
?FZU - 2253海邊躺著一排咸魚，一些有夢想的咸魚成功翻身（然而沒有什么卵用），一些則是繼續當咸魚。一個善良的漁夫想要幫這些咸魚翻身，但是漁夫比較懶，所以只會從某只咸魚開始，往一個方向，一只只咸魚翻過去，翻轉若干只后就轉身離去，深藏功與名。更準確地說，漁夫會選擇一個區間[L,R]，改變區間內所有咸魚的狀態，至少翻轉一只咸魚。
漁夫離開后想知道如果他采取最優策略，最多有多少只咸魚成功翻身，但是咸魚大概有十萬條，所以這個問題就交給你了！
包含多組測試數據。
每組測試數據的第一行為正整數n，表示咸魚的數量。
第二行為長n的01串，0表示沒有翻身，1表示成功翻身。
n≤100000
在漁夫的操作后，成功翻身咸魚（即1）的最大數量。
對于第一個樣例，翻轉區間[2,3]，序列變為1 1 1 1 0。
對于第二個樣例，翻轉整個區間，序列變為1 0 1。
思路：相當于求最達子序列和。把1看成-1，0看成1
代碼：
#include<cstdio> using namespace std; int main() {int n;while(~scanf("%d",&n)){int num=0,j=0,max=-1,x;for(int i=1;i<=n;i++){scanf("%d",&x);if(x==1){j++;num=num-1;if(num<0)num=0;}if(x==0){num=num+1;if(num>max)max=num;}}printf("%d\n",j+max);}return 0; }總結
- 上一篇： grandle下载安装图解
- 下一篇： fzu-2258