Most Valuable Parentheses の解説

括弧列になるための条件として、(を1, )を-1として累積和accを取ったときに、

• $acc_i \ge 0$
• $acc_n = 0$

を満たす必要がある。

acc_i >= 0という条件について考えてみる。i番目までに出てきた(の個数をopen_i、)の個数をclose_iとすると、

$open_i \ge close_i$

が成立する。

また、

$open_i + close_i = i$ なので、

$2open_i \ge i$ となるので、

i番目までに登場する(の個数が $i / 2$ 以上であることがわかる。

よって、これを満たすように前から順番に取れる値の大きい順に取っていけば答え。

fn main() {
    input! {
        t: usize,
    }
    for _ in 0..t {
        solve();
    }
}

fn solve() {
    input! {
        n: usize,
        a: [usize; n * 2]
    }
    let mut ans = a[0];
    let mut set = BTreeSet::new();
    for i in 0..n - 1 {
        let t1 = 2 * i + 1;
        let t2 = 2 * (i + 1);
        set.insert((a[t1], t1));
        set.insert((a[t2], t2));
        
        let a = set.pop_last().unwrap();
        ans += a.0;
    }
    println!("{}", ans);
}