AT_agc048_b.[AGC048B] Bracket Score

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在本题中，我们考虑由 (、)、[、] 组成的字符串。

当字符串 $x$ 满足以下任意一项条件时，称其为良好括号序列：

$x$ 是空字符串。
存在一个良好括号序列 $s$ ，将 (、 $s$ 、) 按此顺序连接后得到 $x$ 。
存在一个良好括号序列 $s$ ，将 [、 $s$ 、] 按此顺序连接后得到 $x$ 。
存在非空的良好括号序列 $s$ 和 $t$ ，将 $s$ 、 $t$ 按此顺序连接后得到 $x$ 。

例如，[]、([()])、()[()] 等是良好括号序列，而 ())、([)] 等不是良好括号序列。

给定一个偶数 $N$ ，以及长度为 $N$ 的整数序列 $A$ 和 $B$ 。对于长度为 $N$ 的良好括号序列 $s=s_1s_2\cdots s_N$ ，定义 $s$ 的分数如下：

$s$ 的分数为各个字符分数的总和。
第 $i$ 个字符（ $1\leq i\leq N$ ）的分数：若 $s_i$ 是 ( 或 )，则为 $A_i$ ；若 $s_i$ 是 [ 或 ]，则为 $B_i$ 。

请你求出长度为 $N$ 的良好括号序列可能取得的最大分数。

输入格式

输入按以下格式从标准输入给出：

$N$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_1$ $B_2$ $\cdots$ $B_N$

输出格式

请输出答案。

输入输出样例

输入#1
```
4
4 2 3 1
2 3 2 4
```
输出#1
```
12
```

输入#2

10
866111664 844917655 383133839 353498483 472381277 550309930 378371075 304570952 955719384 705445072
178537096 218662351 231371336 865935868 579910117 62731178 681212831 16537461 267238505 318106937

输出#2

6629738472

说明/提示

限制条件

$2\leq N\leq 10^5$
$N$ 是偶数
$1\leq A_i\leq 10^9$
$1\leq B_i\leq 10^9$
所有输入的数均为整数。

样例解释 1

当 $s= ()[] $ 时，分数为 $A_1+A_2+B_3+B_4=12$ ，这是最大的分数。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页