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

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ1320 City Merger

問題文

City Merger | Aizu Online Judge
n個の文字列が与えられる.
全ての文字を連続部分文字列として持つような文字列のうち,最小の長さを求めよ.

解法

nが14以下なのでbitDPを疑います.
まず初めに,どの文字列がどの文字列を完全に含有しているかの情報をbitの状態で保存します.
次に,KMP法を用いてある文字を最後に使ったとき,他の文字がどこまで構成されているかの情報を求めます.
順番にこれを用いてbitDPしていけばよいのですが,先にどの文字列からどの文字列を繋げた時に必要な長さがいくつになっていくつの文字列が包含されるかのn^2通りの情報をあらかじめ求めておくとbitDPの遷移が楽になります.
注意点として,3つの文字列にまたがって1つの文字列を構成する必要があるように思えますが,1つの文字列のほうを使えば真ん中の一つの文字列はそれに包含されているのでその必要はないことがわかります.
そのため,2つの文字列間の関係だけ調べればよいことが分かります.
計算量はO(n*2^n)になります.