https://codeforces.com/contest/2064/problem/C
题目大意
给出 $n$ 长的不含 $0$ 的数组 $a$。每次可以选择当前一个正数 $a_i$ 将其加到答案，并将数组的 $i$ 结束的前缀删掉，或者选择某个负数 $a_i$ 将 $- a_i$ 加到答案，并将 $i$ 开始的后缀删掉。问可以得到的最大答案是多少。
$1 \le n \le 2 \times 10^5$。$- 10^9 \le a_i \le 10^9, a_i \neq 0$。
简要题解
观察：
- 总是尽量先取最右边的负数或者最左边的正数，否则我们会比这样取删掉更多数。
- 取完最边上的数之后，总是把其旁边的所有和它符号相同的数取完。假设先取了左边的正数，则显然下次取左侧还会取这里，而取右侧负数也不会删掉这个数。因此我们可以将所有的符号相同的数压缩在一起变成数组 $b$。
- 所以我们其实就是要处理一个 -+-+-+ 这样的序列的最优值。
对于 3 由于我们每次都是删除边上的一个，容易想到这是一个区间 dp 的转移
$$ dp[l][r] = max(dp[l + 2][r] + b[l + 1], dp[l][r - 2] + b[r - 1]) $$但显然这是 $O(n ^ 2)$ 的复杂度无法通过本题。这里我们注意到，如果最后处理的区间位置确定，我们就知道其左右各做了多少次区间收缩，而无论收缩顺序如何，其权值是确定的，因此我们只要枚举左右各进行 $i$ 次和 $\frac{|b|}{2} - i$ 次收缩即可。
复杂度
$T$：$O(n)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
/*
+ + - - - + + + - - - + - -
- - - + + + - - - +
*/
inline int sgn(LL x) { return (x > 0) - (x < 0); }
void solve() {
int n; cin >> n;
vector<int> a(n);
for (int& i : a) cin >> i;
vector<LL> b;
for (int i = 0; i < n; ) {
int j = i;
LL cur = 0;
while (j < n && sgn(a[j]) == sgn(a[i])) {
cur += a[j];
j++;
}
b.push_back(cur);
i = j;
}
int l = 0, r = b.size() - 1;
LL ans = 0;
if (b[l] > 0) {
ans += b[l];
l++;
}
if (l <= r && b[r] < 0) {
ans += -b[r];
r--;
}
if (l <= r) {
int len = (r - l + 1) / 2;
vector<LL> c;
vector<LL> d;
for (int i = l; i <= r; i += 2) {
c.push_back(b[i + 1]);
d.push_back(-b[i]);
}
for (int i = 1; i < len; i++) {
c[i] += c[i - 1];
}
for (int i = len - 2; i >= 0; i--) {
d[i] += d[i + 1];
}
LL mx = max(c[len - 1], d[0]);
for (int i = 0; i + 1 < len; i++) {
cmax(mx, c[i] + d[i + 1]);
}
ans += mx;
}
cout << ans << '\n';
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] B. Variety is Discouraged - Codeforces Round 1005 (Div. 2)