Dashboard - Codeforces Round 899 (Div. 2) - Codeforces

C. Card Game

题意

有n张卡牌，每张卡牌上有一个整数（可能是负数），按顺序盖好， 你可以选择任意次如下操作，使得你最终的得分最多：

  • 选择一个奇数 $i$ ,将第 $i$ 个数从牌堆中取出，然后获得这张牌上对应的分数
  • 选择一个偶数 $i$ ,将第i个数从牌堆中丢弃，不获得对应分数

问进行若干次操作后（可以为0次） 最多可以获得多少分数。

思路

由于牌上的数可以是负数，所以我们要尽量多的选择正数，然后尽量少地选择负数。

我们可以把连续的一段负数（或者连续的一段正数） 称为 负数串（正数串）
对于任意一个长度大于等于2的负数串，我们可以通过不断舍弃偶数，使得最终这个串只剩下一个或零个负数
对于任意一个长度大于等于2的正数串，我们可以通过不断选取奇数，来让这个串最终只剩一个或零个整数

这样化简到最后，一定会是 负正负正... 的串

因此我们只需要考虑负数在奇数，正数在偶数的情况：
这时候我们就需要选择两种情况中的较优解：1. 选取负数，然后选取后面跟着的正数。 2.负数和正数都不选择。并且我们只需要做一次这样的取舍，就可以获得选择之后所有正数的机会。

因此我们可以使用后缀和记录后$i$个正数的和。然后遍历数组，如果到达了数组的奇数位，则选择 不选或者 选上该位的数字之后再 加上此后的所有正数；如果到达了数组的偶数位，则 可以通过抛弃这一位来选择此后所有的正数。 最终找到最优的选择位置和方案即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
#include<vector>
using namespace std;
#define int long long//注意这题会爆int
const int N = 1e5+5;

signed main(){
    int t;
    cin>>t;
    while(t--){
        int n,ans = 0;
        cin>>n;
        vector<int> a(n+5);
        vector<int> sum(n+5);
        for(int i = 1;i<=n;i++) cin>>a[i];
        for(int i = n;i>0;i--){//求后缀中的正数和
            sum[i] = sum[i+1];
            if(a[i] > 0) sum[i] += a[i];
        }
        for(int i = 1;i <= n;i++){
            if(i % 2 == 1) ans = max(ans,sum[i+1] + a[i]);
            else ans = max(ans,sum[i + 1]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

D