PAST2K
from 第二回 アルゴリズム実技検定
PAST2K
考えたこと
変更と削除を行うことで対応の取れた括弧にする問題
文字ごとに変換コストと削除コストが決まっている
N=3000
変換してから削除することにメリットはないので「何もしない、変換する、削除する」の三択
括弧をプラマイ1、削除を0とすれば「X番目までの和」をYとしてDPができそう
対応した括弧は、途中で負にならず、最後で0になる
値の範囲は0〜N
N^2なので間に合う
AC
code:python
def solve(N, S, CS, DS):
INF = 9223372036854775807
table = INF * (N + 1) # tableN is sentinel
table0 = 0
for i in range(N):
new_table = INF * (N + 1)
if Si == "(":
d = 1
else:
d = -1
for j in range(N):
new_tablej = min(
tablej - d, # no change
tablej + d + CSi, # change
tablej + DSi, # delete
)
table = new_table
return table0
括弧列は上り下り
動的計画法
範囲上下に番兵