別解 JOIoc 2020 - Furniture 概要
Author : Cyanmond
解法
まず、家具を置かない操作のうち一番初めに行われるものを$ O(NM)で求めることを目標にする。これは簡単な DP で問題ない。求めた結果$ (x, y)となったとする。
このとき、$ (x, y)の家具を置くクエリは元々なかったものとして再び DP を行う。すると、 2 番目に行われる家具を置かない操作もわかる。
これを続けることで、$ k番目までの家具を置かない操作を$ O(kNM)で求めることができる。
ところで、家具を置かないような操作は高々$ N + M - 3回である。
証明 : $ (1, 1)から$ (N, M)のパスに含まれる頂点数は$ N + M - 1個であるので、$ N + M個以上クエリで家具を置かないことを選択された頂点が存在することはありえない。$ (1, 1)と$ (N, M)は制約上クエリが来ないことを加味すると、家具を置かないことを選択される頂点は高々$ N + M - 3個しかないことがわかる。
よって、この解法の計算量は$ O(NM(N + M))となる。
$ N, M \leq 1000なので、 dp で実際に再計算する部分を限定するなどの工夫を加えれば oj.uz においても問題なく AC できる。