2015-10-15から1日間の記事一覧
マッチングの最小化をする。 想定解法では変なことをしてO(N^2)であるが、見るからにMonge DPのDivide and Conquerテクなので、終了。 距離の和の計算で嵌った。 (そういえばDPの式ですが、dp[i][j]: i個目の余った点(サイズ1以上)でj個覆ったときの最小コス…
マッチングの最小化をする。 想定解法では変なことをしてO(N^2)であるが、見るからにMonge DPのDivide and Conquerテクなので、終了。 距離の和の計算で嵌った。 (そういえばDPの式ですが、dp[i][j]: i個目の余った点(サイズ1以上)でj個覆ったときの最小コス…