Card Game

题面翻译

有一叠 $n$ 张卡牌的有序牌堆，每张牌上有一个整数数值 $a_i$，你可以按照如下的方案获取得分，得分初始是 $0$。

每次你可以做下面三种操作之一：
- 选择奇数 $i$，则选择牌堆从上往下数第 $i$ 张牌弃掉后获得等同于其卡面上数值的分数；
- 选择偶数 $i$，则选择牌堆从上往下数第 $i$ 张牌弃掉后，什么都不做；
- 直接结束游戏，你可以在任意时刻结束游戏，无论牌桌上有没有剩余的牌。

求你能获得的最大分数。

$1\le t \le 10^4 , 1\le n,\sum n \le 2\times10^5,-10^9\le a_i \le 10^9 $

题目描述

There are $ n $ cards stacked in a deck. Initially, $ a_{i} $ is written on the $ i $ -th card from the top. The value written on a card does not change.

You will play a game. Initially your score is $ 0 $ . In each turn, you can do one of the following operations:

• Choose an odd $ ^{\dagger} $ positive integer $ i $ , which is not greater than the number of cards left in the deck. Remove the $ i $ -th card from the top of the deck and add the number written on the card to your score. The remaining cards will be reindexed starting from the top.
• Choose an even $ ^{\ddagger} $ positive integer $ i $ , which is not greater than the number of cards left in the deck. Remove the $ i $ -th card from the top of the deck. The remaining cards will be reindexed starting from the top.
• End the game. You can end the game whenever you want, you do not have to remove all cards from the initial deck.

What is the maximum score you can get when the game ends?

$ ^{\dagger} $ An integer $ i $ is odd, if there exists an integer $ k $ such that $ i = 2k + 1 $ .

$ ^{\ddagger} $ An integer $ i $ is even, if there exists an integer $ k $ such that $ i = 2k $ .

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^{4} $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^{5} $ ).

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ -10^{9} \le a_i \le 10^{9} $ ).

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^{5} $ .

输出格式

For each test case, print a single integer — the maximum score you can get when the game ends.

样例 #1

样例输入 #1

4
4
-4 1 -3 5
4
1 -2 3 -4
3
-1 3 -5
1
-1

样例输出 #1

5
4
2
0

提示

In the first test case, one can get the score of $ 5 $ as follows:

1. In the first turn, choose $ i=2 $ . Your score remains $ 0 $ and the numbers written on the cards from the top will become $ [-4, -3, 5] $ .
2. In the second turn, choose $ i=3 $ . Your score will become $ 5 $ and the numbers written on the cards from the top will become $ [-4, -3] $ .
3. In the third turn, end the game with the score of $ 5 $ .

In the second test case, one can get the score of $ 4 $ as follows:

1. In the first turn, choose $ i=3 $ . Your score will become $ 3 $ and the numbers written on the cards from the top will become $ [1, -2, -4] $ .
2. In the second turn, choose $ i=1 $ . Your score will become $ 4 $ and the numbers written on the cards from the top will become $ [-2, -4] $ .
3. In the third turn, end the game with the score of $ 4 $ .

In the third test case, one can get the score of $ 2 $ as follows:

1. In the first turn, choose $ i=1 $ . Your score will become $ -1 $ and the numbers written on the cards from the top will become $ [3, -5] $ .
2. In the second turn, choose $ i=1 $ . Your score will become $ 2 $ and the numbers written on the cards from the top will become $ [-5] $ .
3. In the third turn, end the game with the score of $ 2 $ .

发现大于等于3的所有整整数都可以取到，为什么，（从从后往前取不改变要取的奇偶性），在偶数位的正整数，在前面取一个就会改变成奇数位，则又可以从后往前取，在最后如果还有没办法取得偶数位的正数，看第一第二个，第一第二个都是正的都取，第一个是正，取第一个，第二个正，第一个负，看看大小取，其余情况不取，好，这样我们就发现无论第一第二个怎么样，都会拿出一个来改变后面的数的奇偶性，这样就可以取后面的偶数位的正数了，如果第一加第二小于0或者两个都是负数，则拿第二个出来，不改变分数，又可以取后面的数，两个都要取的情况下可以先取一个，再取后面的数，再取第二个

const int N = 2e5+10;
int a[N];
int dp[N];
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int ans = 0;
    for (int i = 3; i <= n; i++) ans += max(a[i], (int)0);
    if (a[1] > 0 && a[2] > 0) ans += a[1] + a[2];
    else if (a[1] > 0) ans += a[1];
    else if (a[1] + a[2] > 0) ans += a[1] + a[2];
    cout << ans << '\n';
    for (int i = 1; i <= n; i++) a[i] = 0;
}