\(O(N^{2})\) は通る． 全探索するとき， \(for \ i \in N\) はこれ以上簡単に出来なさそう． そこで，残りを\(O(N)\) で押さえたい．
( を+1, ) を-1 とみる． 計算量を無視して，持っておきたい情報（状態）を考えてみる．
- 今調べている場所の左に，+1 がいくつあるか
- 今調べている場所の左に，-1 がいくつあるか
- 和がいくつか
- いくつ削除したか
これらは，「和がいくつか」という状態にまとめられる．
正しい括弧列であることの必要十分条件は，
- 常に和が0以上かつ，
- 最後に和が0になること．
よって， \(dp_{i,t} := [0,i) まで完了していて，和が\ t \ のときの min cost \) として dp．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m, k, q;
cin >> n;
string s; cin >> s;
vll c(n), d(n);
cinv(c);
cinv(d);
vll dp(n+1, INFL);
dp[0] = 0;
rep(i,s.length()){ // rem : s.length() != n in general
vll old(n+1, INFL);
swap(dp, old);
rep(t,i+1){ // rem : t = i も含む
// i-th
// -> +
if(s[i] == ')'){
chmin(dp[t+1], old[t] + c[i]);
}else{
chmin(dp[t+1], old[t]);
}
// -> -
if(t >= 1){
if(s[i] == '('){
chmin(dp[t-1], old[t] + c[i]);
}else{
chmin(dp[t-1], old[t]);
}
}
// -> (del)
chmin(dp[t], old[t] + d[i]);
}
}
cout << dp[0] << endl;
return 0;
}
