No.3148 Min-Cost Destruction of Parentheses
タグ : / 解いたユーザー数 25
作問者 :
Nauclhlt🪷
/ テスター :
naniwazu
👑 
p-adic
問題文
対応が取れた括弧列の定義
文字列 $X$ が対応が取れた括弧列であるとは、次を満たすことをいいます。
- $X$ に連続部分文字列として含まれる
()を削除する操作を $0$ 回以上繰り返して $X$ を空文字列とすることができる
例えば()(())や()()()()は対応が取れた括弧列ですが、))((や)()()(などは対応が取れた括弧列ではありません。
長さ $2N$ の対応が取れた括弧列 $S$ があります。はじめ、$S$ にはちょうど $N$ 個の(が含まれますが、これらを左から開き括弧 $1, 2, \cdots, N$ と呼ぶことにします。
また、開き括弧 $i$ に対応する)を閉じ括弧 $i$ と呼び、開き括弧 $i$ と閉じ括弧 $i$ の組を対応 $i$ と呼びます。ここで「対応する」とは対応が取れた括弧列の定義において同時に削除されることをいいます。
$S$ に変更が加えられても括弧に割り当てられた番号は変わらないことに注意してください。例えば、対応 $2$ が削除されても 対応 $3$ が新たに対応 $2$ になるようなことはありません。
長さ $N$ の非負整数列 $A=(A_1, A_2, \cdots, A_N)$ があり、また、はじめ $x=0$ です。nauclhltくんはこれから $S$ が空文字列になるまで以下の操作を繰り返します。
- $S$ に連続部分文字列として含まれる
()をひとつ選び、削除する。選んだ()が対応 $k$ のとき、$x$ に $A_k$ を加算する。その後、コストが $x$ かかる
操作を終えるまでにかかるコストの合計としてあり得る最小値を求めてください。
入力
$N$ $S$ $A_1\ A_2\ \cdots\ A_N$
- $1\leq N\leq 10^5$
- $S$ は長さ $2N$ の対応が取れた括弧列
- $0\leq A_i\leq 500$
- $N, A_i$ は整数
出力
コストの合計の最小値を $m$ として、次の形式で $1$ 行に出力してください。
$m$
最後に改行してください。
サンプル
サンプル1
入力
3 ()(()) 2 5 1
出力
12
コストの合計 $12$ は以下のように達成できます。
- 1回目の操作で、対応 $3$ である
()を選ぶ。$x=1$ となり、コストが $1$ かかる - 2回目の操作で、対応 $1$ である
()を選ぶ。$x=3$ となり、コストが $3$ かかる - 3回目の操作で、対応 $2$ である
()を選ぶ。$x=8$ となり、コストが $8$ かかる
コストの合計が $12$ 未満で操作を終えることはできないため、答えは12です。
サンプル2
入力
4 ()()()() 1 1 1 1
出力
10
サンプル3
入力
3 ()(()) 1 0 1
出力
4
コストの合計 $4$ は以下のように達成でき、これが最小です。
- 1回目の操作で、対応 $3$ である
()を選ぶ。$x=1$ となり、コストが $1$ かかる - 2回目の操作で、対応 $2$ である
()を選ぶ。$x=1$ となり、コストが $1$ かかる - 3回目の操作で、対応 $1$ である
()を選ぶ。$x=2$ となり、コストが $2$ かかる
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。