FZU 2253 salty fish

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 <stdio.h>
2 #include <string.h>
3 #include <algorithm>
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
",ans + num);
42 }
43
44 return 0;
45 }

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！