読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

TopCoder SRM 686 (Div. 1) Easy. BracketSequenceDiv1

起床に失敗しました。

問題概要

()[] で構成された文字列が与えられる。正しい括弧列にするような文字の削除方法は何通りあるだろうか。

解法

区間 DP。

次のような関数を定義する。

  • f(l,r):=区間 [l,r] を使って作ることのできる正しい括弧列の総数

遷移パターンは、

  • s[l] と s[i] を対応させる
  • s[l] を削除

の2通り。

s[l] と s[i] を対応させるパターン数は f(l+1,i-1)*f(i+1,r) 通り。s[l] を削除するパターン数は f(l+1,r) 通り。

f:id:pekempey:20160329153910p:plain

TopCoder SRM 686 (Div. 1) Easy. BracketSequenceDiv ...

いかにも区間 DP で解けそうな問題。