問題概要

$H*W$ のグリッドがあり、これを列ごとに下に沈めていって全部消すことを考える。
1つの列は1つずつしか下に沈めることはできず、沈めるときは、左右で同じ要素が隣り合っている場所の数と同じコストがかかる。
すべてを沈め終わるまでのコストの総和を最小化せよ。

考察

制約が $H,W$ ともに小さめなので、DPで解けそう。
状態を全部場合分けすると $(H+1)^W$ 個の状態数があるので、考察をして減らしたい。
それでも、これだけの量の状態数を問題ない量にエンコードするのは実質無理そう
1つの列を下げるとき、気にしなければいけないのは隣り合った列の状態だけ
隣り合った列だけ見てどうにかできないか？
よくよく考えると、隣り合っているある2つの列に対して、相対的な順番だけを考えればその2つの間での最適解を、他の列を一切考えずに達成できることが分かる
考えていない列の操作は、考えているところとは全く関係ないので、それぞれ都合のいいところに突っ込めばいい
これで隣り合っている $W-1$ 箇所についてDPをして足し合わせれば答えが出る
$dp[i][j]=$ 左に $i$ 個、右に $j$ 個残っているときのコストの総和の最小値　としてDPをしたいが、遷移の計算に毎回 $O(H)$ かかるので、全体で $O(H^3W)$ となり、破滅してしまう
$cost[i][j]=$ 左に $i$ 個、右に $j$ 個残っているときの次の操作にかかるコスト　とすると、$cost$ もDPを用いて $(H^2)$ で求められ、これで遷移が $O(1)$ にできた
これで全体計算量が $O(H^2W)$ となって、大勝利

この問題めちゃくちゃ好きです。とてもすき。（すぐ解けたので）