No.3148 Min-Cost Destruction of Parentheses
Problem Statement
Definition of a balanced parenthesis sequence
A string $X$ is a balanced parenthesis sequence if it satisfies the following.
- $X$ can be made into the empty string by repeating, $0$ or more times, the operation of deleting a
()contained in $X$ as a substring
For example, ()(()) and ()()()() are balanced parenthesis sequences, but ))(( and )()()( are not balanced parenthesis sequences.
There is a balanced parenthesis sequence $S$ of length $2N$. Initially, $S$ contains exactly $N$ occurrences of (; we call these opening brackets $1, 2, \cdots, N$ from left to right.
Also, the ) corresponding to opening bracket $i$ is called closing bracket $i$, and the pair of opening bracket $i$ and closing bracket $i$ is called pair $i$. Here, "corresponding" means being deleted at the same time in the definition of a balanced parenthesis sequence.
Note that the numbers assigned to the brackets do not change even when $S$ is modified. For example, even if pair $2$ is deleted, pair $3$ does not newly become pair $2$.
There is a sequence of non-negative integers $A=(A_1, A_2, \cdots, A_N)$ of length $N$, and initially $x=0$. nauclhlt will now repeat the following operation until $S$ becomes the empty string.
- Choose one
()contained in $S$ as a substring and delete it. If the chosen()is pair $k$, add $A_k$ to $x$. After that, a cost of $x$ is incurred
Find the minimum possible total cost incurred by the end of the operations.
Input
$N$ $S$ $A_1\ A_2\ \cdots\ A_N$
- $1\leq N\leq 10^5$
- $S$ is a balanced parenthesis sequence of length $2N$
- $0\leq A_i\leq 500$
- $N, A_i$ are integers
Output
Let $m$ be the minimum total cost. Output it on $1$ line in the following format.
$m$
Print a newline at the end.
Sample
Sample 1
Input
3 ()(()) 2 5 1
Output
12
A total cost of $12$ can be achieved as follows.
- In the 1st operation, choose the
()that is pair $3$. Now $x=1$, and a cost of $1$ is incurred - In the 2nd operation, choose the
()that is pair $1$. Now $x=3$, and a cost of $3$ is incurred - In the 3rd operation, choose the
()that is pair $2$. Now $x=8$, and a cost of $8$ is incurred
It is impossible to finish the operations with a total cost less than $12$, so the answer is 12.
Sample 2
Input
4 ()()()() 1 1 1 1
Output
10
Sample 3
Input
3 ()(()) 1 0 1
Output
4
A total cost of $4$ can be achieved as follows, and this is the minimum.
- In the 1st operation, choose the
()that is pair $3$. Now $x=1$, and a cost of $1$ is incurred - In the 2nd operation, choose the
()that is pair $2$. Now $x=1$, and a cost of $1$ is incurred - In the 3rd operation, choose the
()that is pair $1$. Now $x=2$, and a cost of $2$ is incurred
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
nauclhlt
naniwazu