https://atcoder.jp/contests/agc048/tasks

B - Bracket Score

 

题意：给定A，B数组，要用 ‘(’, ‘)’, ‘[’, ‘]’ 构造出合法的括号序列，若位置 ii 为 ‘(’ 或 ‘)’，则该位置贡献 AiA_i，否则贡献 BiB_i，求最大总贡献。

贪心

先把所有位置上都放小括号，由于题目规定了 n 为偶数，所以必定合法。

再尝试修改一些位置上为中括号，每次选择两个间隔为偶数，且都为小括号的位置，并修改，这样每对小括号以及每对中括号的长度都为偶数，必定能够构造出合法序列。

所以只要贪心地每次选择一对修改后贡献最大的位置变为中括号。

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
#include <bits/stdc++.h>
#define debug(x) cout << ##x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int n;
ll a[N], b[N];
ll ans;
priority_queue<ll>q[2];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%lld", &a[i]), ans += a[i];
	for (int i = 1; i <= n; i++)scanf("%lld", &b[i]);
	for (int i = 1; i <= n; i++) {
		q[i & 1].push(b[i] - a[i]);
	}
	while (1) {
		if (!q[0].empty() && q[0].top() + q[1].top() > 0) {
			ans += q[0].top() + q[1].top();
			q[0].pop();
			q[1].pop();
		}
		else break;
	}
	printf("%lld\n", ans);
	return 0;
}