問題一覧 > 通常問題

No.2591 安上がりな括弧列

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 68
作問者 : H20H20 / テスター : minatominato
1 ProblemId : 10351 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-12-10 23:06:53

問題文

( と ) のみからなる文字列を括弧列と呼ぶことにします。

長さ $2N$ の括弧列 $S$ があります。

$i$ 文字目は $A_i$ のコストを払うことで、 (を )に、 )を (に入れ替えることができます。

括弧列 $S$ を整合している状態にするためのコストの最小値を答えてください。

括弧列 $S$ に対して、連続する $2$ 文字が () である箇所を除去する操作を $0$ 回以上繰り返すことで空文字にできるとき、括弧列 $S$ は整合しているといいます。

入力

$N$
$S$
$A_1$ $A_2$ $\ldots$ $A_{2N}$

制約

  • $ 1 \le N \le 1000$
  • $|S|=2N$
  • $S$ は(と)のみからなる
  • $ 1 \le A_i \le 10^{9}$
  • $N,A_i$ は整数

出力

括弧列 $S$ を整合している状態にするためのコストの最小値を出力してください。

最後に改行してください。

サンプル

サンプル1
入力
3
)(((()
10 22 3 5 2 13
出力
15

$1$ 文字目と $3$ 文字目と $5$ 文字目を入れ替えることで括弧列は(()())となり整合している状態となります。 コストは $15$ でこれより小さなコストで整合させることはできないため、 $15$が答えとなります。

サンプル2
入力
4
()(()())
3141592 653589 793238 462643 38327 9502884 1971 69399375
出力
0

元から整合している場合もあります。

サンプル3
入力
5
((((((((((
1 2 3 4 5 6 7 8 9 10
出力
30

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。