参考：https://info.atcoder.jp/entry/algorithm_lectures/min_plus_convolution

dp による解法を考え，それを凸数列に対する操作に言い換えることで，公式解説の貪欲法と同じ解法を導出することができます．

ある時点までで選ぶ必要がある開きカッコの個数の最小個数が \(k\) であるとき，\(k+i\) 個の開きカッコを選んだ場合の最適解での利得を \(\mathrm{dp}[i]\) とします．

次の操作ができればよいことになります．

• \(\mathrm{newdp}[i] = \max(\mathrm{dp}[i], \mathrm{dp}[i-1]+a)\) として dp テーブル全体を更新
• dp テーブルから先頭の要素を削除する．

ひとつめの操作は次の \(2\) つの列の max-plus convolution です．

• \(\mathrm{dp}\)
• \([0,a]\)

このことから，常に dp テーブルは上凸であることが分かります．また折れ線グラフを考えれば，操作は

• 傾き \(a\) で \(x\) 座標幅が \(1\) であるような線分の挿入
• 左端にある最も大きな傾きの線分を削除

というようになります．折れ線グラフの線分の多重集合を priority queue で保持しながらこれを行うことを考えると，公式解説と同じアルゴリズムが得られます．