AOJ0145: Cards
Vol.12がだんだんきつくなってきたのでここらでVol.01の残りを掃除でもしようかと。
方針
solve(a,b):=a番目の山からb番目の山までを纏めるのに掛かるコストの最小値
としてメモる。
どこで2つに分けるかを考えて計算していく。
a ... b | c ... d
として、左右それぞれをまとめてから|の位置で合わせるとすると
solve(a,d) = solve(a,b) + solve(c,d) + (aの上) * (bの下) * (cの上) * (dの下)
になる。(solve(a,a)=0)
メモ化再帰はDPの一種なんだろうけど、ボトムアップ感があって
配る/貰うDPとはまた違う感覚があるのでもっと練習が必要。
