ABC008-D問題
蟻本で似た問題（P121, Bribe the Prisoners）を見たことがあったので同じように考えて実装しました。機械を動かしたあとその機械で取った金塊で分断された場所は互いに関係しない独立した場所です。なので、ある機械を動かしたときに得られる金塊の数は
（１）機械を動かして得られる金塊
（２）分断されたそれぞれのエリアで得られる金塊
の和になります。それぞれのエリアについて再帰的に考えていけば得られる最大の金塊数を求められます。dp[sx][sy][fx][fy]を左上を(sx, sy)、右下を(fx, fy)としたエリアで得られる金塊としてメモ化再帰で実装しました。境界条件の部分は番兵法つかったほうが良さそう…
範囲内を全て探索しているところを機械がある点に絞れば100点の制約でも間に合いました。
