https://vjudge.net/problem/FZU-2253

题意：略

思路：

一开始改变区间，还以为是线段树。。。还是dp的题做得太少了。

这题一开始我们可以统计出一共有多少只翻身的咸鱼，对于每一个位置上，如果是1，那么改变它，翻身咸鱼数少1，如果是0，那么就加1。所以，就可以直接利用动态规划，dp[i]表示翻转到第i位时的翻身的增加数目，可能为负，因为至少翻转一只鱼。转移方程dp[i] = max(tmp,dp[i-1] + tmp),tmp表示当前的格子是翻还是不翻。切记ans一开始必须等于dp[0],dp[0]取决于第一个格子是翻还是不翻。一开始直接把ans赋值为0，wa了无数次。比如当序列为 1 1 1 1 1时，ans = 0的答案是5，但是正确答案应该是4。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 int a[100005],dp[100005]; 7  8 int main() 9 {10     int n;11 12     while (scanf("%d",&n) != EOF)13     {14         int num = 0;15 16         for (int i = 0;i < n;i++)17         {18             scanf("%d",&a[i]);19 20             if (a[i] == 1) num++;21         }22 23 24         if (a[0] == 1) dp[0] = -1;25         else dp[0] = 1;26 27         int ans = dp[0];28 29         for (int i = 1;i < n;i++)30         {31             int tmp;32 33             if (a[i] == 1) tmp = -1;34             else tmp = 1;35 36             dp[i] = max(tmp,dp[i-1] + tmp);37 38             ans = max(ans,dp[i]);39         }40 41         printf("%d\n",ans + num);42     }43 44     return 0;45 }