JOI 13春合宿 Mascots(難易度8)
マスコットが置いてあるマスをすべて含むような最小の長方形を作り, それを拡大していくのが最適である.
まず, $ dp_{i, j} := 上下方向に$ i回, 左右方向に$ j回長方形を拡大したときの少し幸せになる回数が最大になる操作方法について, 順番を考慮しない場合の数 を求める.
すると, $ dp_{0, 0} = (最初の長方形のマスのうち, 空いているものの個数)! となり, 遷移は$ dp_{i + 1, j} = dp_{i + 1, j} + dp_{i, j} \cdot (C - j)!, dp_{i, j + 1} = dp_{i, j + 1} + dp_{i, j} \cdot (R - i)!となる.
DPを計算して直接求めようとするのではなく, 一旦別のものをDPで求めてそこから計算するというタイプ. 見えにくい.