← 返回题目列表

AtCoder · abc407_e

H. 最有价值的括号

中文机器翻译题面 查看原题

分数: 450 点

问题陈述

给你一个非负整数序列 A = (A_1,\dots,A_{2N}) 长度 2N.

定义括号序列的分数 s 长度 2N 如下:

  • 对于每个位置 i 其中 i- 第一个字符 s is ),设置 A_i to 0,然后取所有元素的总和 A.

找到长度正确的括号序列的最大可能得分 2N.

你被给予 T 测试用例;逐一解决。

什么是正确的括号序列? 正确的括号序列是可以通过重复删除等于的子字符串来减少为空字符串的字符串 ().

约束

  • 1 \le T \le 500
  • 1 \le N \le 2 \times 10^{5}
  • 对于每个输入文件,总和 N 所有测试用例最多 2 \times 10^{5}.
  • 0 \le A_i \le 10^{9} (1 \le i \le 2N)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
\textrm{case}_1
\textrm{case}_2
\vdots
\textrm{case}_T

\textrm{case}_i 代表 i- 第一个测试用例。每个测试用例均按以下格式给出:

N
A_1
A_2
\vdots
A_{2N}

输出

输出 T 行。的 i- 第行 (1 \le i \le T)应包含以下问题的答案 i- 第一个测试用例。


示例输入 1

2
3
400
500
200
100
300
600
6
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000

示例输出 1

1200
6000000000

在第一个测试用例中,选择正确的括号字符串 (())() 给出的分数为 400+500+0+0+300+0=1200.

没有正确的括号字符串会产生更高的分数,所以答案是 1200.

请注意,正如本示例的第二个测试用例一样,答案可能超出 32 位整数范围。