首页 > 代码库 > FZU 2253 salty fish

FZU 2253 salty fish

2024-11-02 16:31:40   204人阅读

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\n",ans + num);
42     }
43 
44     return 0;
45 }

 

FZU 2253 salty fish


联系
我们