No.2591 Cheap Bracket Sequence
H20
minatoProblem Statement
A string consisting only of ( and ) is called a bracket sequence.
There is a bracket sequence $S$ of length $2N$.
By paying a cost of $A_i$, you can change the $i$-th character from ( to ), or from ) to (.
Find the minimum cost required to make the bracket sequence $S$ balanced.
For a bracket sequence $S$, if it can be turned into the empty string by repeating, $0$ or more times, the operation of removing a place where $2$ consecutive characters are (), then the bracket sequence $S$ is said to be balanced.
Input
$N$
$S$
$A_1$ $A_2$ $\ldots$ $A_{2N}$
Constraints
- $ 1 \le N \le 1000$
- $|S|=2N$
- $S$ consists only of
(and) - $ 1 \le A_i \le 10^{9}$
- $N,A_i$ are integers
Output
Output the minimum cost required to make the bracket sequence $S$ balanced.
Print a newline at the end.
Sample
Sample 1
Input
3 )(((() 10 22 3 5 2 13
Output
15
By flipping the $1$-st, $3$-rd, and $5$-th characters, the bracket sequence becomes (()()), which is balanced.
The cost is $15$, and it cannot be made balanced at a smaller cost, so the answer is $15$.
Sample 2
Input
4 ()(()()) 3141592 653589 793238 462643 38327 9502884 1971 69399375
Output
0
The sequence may already be balanced from the start.
Sample 3
Input
5 (((((((((( 1 2 3 4 5 6 7 8 9 10
Output
30
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。