Particles

题面翻译

给定一个长度为 $n$ 的数列，你需要删若干个数，使得数列只剩下一个数。

若删的数为 $a_i$，那么 $a_{i-1}$ 和 $a_{i+1}$ 将会合并（当删的数为当前第一或最后一个数时，没有数会合并）。

求最后一个数的最大值。

题目描述

You have discovered $ n $ mysterious particles on a line with integer charges of $ c_1,\dots,c_n $ . You have a device that allows you to perform the following operation:

  • Choose a particle and remove it from the line. The remaining particles will shift to fill in the gap that is created. If there were particles with charges $ x $ and $ y $ directly to the left and right of the removed particle, they combine into a single particle of charge $ x+y $ .

For example, if the line of particles had charges of $ [-3,1,4,-1,5,-9] $ , performing the operation on the $ 4 $ th particle will transform the line into $ [-3,1,9,-9] $ .

If we then use the device on the $ 1 $ st particle in this new line, the line will turn into $ [1,9,-9] $ .

You will perform operations until there is only one particle left. What is the maximum charge of this remaining particle that you can obtain?

输入格式

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 $ c_1,\dots,c_n $ ( $ -10^9 \le c_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, output one integer, the maximum charge of the remaining particle.

样例 #1

样例输入 #1

1
2
3
4
5
6
7
3
6
-3 1 4 -1 5 -9
5
998244353 998244353 998244353 998244353 998244353
1
-2718

样例输出 #1

1
2
3
9
2994733059
-2718

提示

In the first test case, the best strategy is to use the device on the $ 4 $ th particle, then on the $ 1 $ st particle (as described in the statement), and finally use the device on the new $ 3 $ rd particle followed by the $ 1 $ st particle.

In the second test case, the best strategy is to use the device on the $ 4 $ th particle to transform the line into $ [998244353,998244353,1996488706] $ , then on the $ 2 $ nd particle to transform the line into $ [2994733059] $ . Be wary of integer overflow.

In the third test case, there is only one particle, so no operations can be performed.

题解

题目解析

对这个粒子的碰撞分析, 可以得出两个结论:

  • 粒子只能与相同奇偶性的粒子合并.
  • 我们可以选择奇偶性相同的任意粒子进行合并(中间可以空,不要求连续).

可以归纳总结, 经过有限次合并和边侧删除之后一定会剩下一个粒子. 并且呢, 删除靠边位置的粒子并不会造成合并. 于是我们就可以选择任意相同奇偶性的对结果有贡献的粒子合并.

但是还是要特判粒子都小于等于 $0$ 的情况, 要不然会出错.

一定要看数据范围!!! 不开 Long Long 遗憾终生!!!

AC代码

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define CIN_ ios::sync_with_stdio(0)
#define CIN cin.tie(0)
#define MAXN(size) const long long MAXN = size + 100
#define MOD(size) const long long MOD = size
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(i,a,n) for(int i=a;i<=n;++i)
#define fb(i,a,n) for(int i=a;i>=n;--i)
#define T_ int T;cin >> T;while(T--)
typedef long long ll;
typedef unsigned long long ull;

//没开 long long 炸了一次...
signed main(){
	T_{
		std::vector<ll> a,b;
		ll n,cunt=0;
		cin >> n;
		fa(i,1,n){
			ll temp;
			cin >> temp;
			if(n == 1){//特判一下1的情况
				cout << temp << endl;
				break;
			}
			if(temp <= 0) cunt++;
			if(i&1) a.push_back(temp);
			else b.push_back(temp);
		}
		if(n == 1) continue;//特判一下1的情况
		ll ans = -1e18;
		if(cunt == n){
			fa(i,0,a.size()-1){
				ans = max(ans,a[i]);
			}
			fa(i,0,b.size()-1){
				ans = max(ans,b[i]);
			}
		}else{
			ll ans1=0,ans2=0;
			fa(i,0,a.size()-1){
				ans1 += max((ll)0,a[i]);
			}
			fa(i,0,b.size()-1){
				ans2 += max((ll)0,b[i]);
			}
			ans = max(ans1,ans2);
		}
		cout << ans << endl;
	}
	return 0;
}