Assembly line (UVa Live Archive Europe Southwestern 2010)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2962

問題

m種類の文字から構成されるn文字の文字列が与えられる。また2つの文字を合成した時にどの文字が何分でできるかの表も与えられる。最小の時間で1文字にせよ。
n<=200
1<=m<=26

解法

DP[l][r][c]を計算する。意味は区間[l,r]を合成しcの文字を作るのに最短な時間を表す。あとはこのDPをO(n^3m^2)で計算すれば良い。メモ化再帰だと間に合わなかったので普通にDPで計算した。