解説
各島は「全部残す」か「全部消す」かのどちらかとしてよいです。残す島の集合を T とすると、費用は次の 2 つの和です。
- T に含まれない島の面積の合計
- T の島どうしをつなぐのに必要な、埋め立てるマスの最小値
2 つ目は陸地のマスの重みを 0、海のマスの重みを 1 とした頂点重みつきの最小シュタイナー木です。
c(v) をマス v の重みとします(陸地なら 0、海なら 1)。また、dp[S][v] を次のように定義します。
dp[S][v] = マス v を含み、集合 S のすべての島のマスを含む連結なマス集合のうち、含まれる海のマスの個数の最小値
島 i に含まれるマス v を 1 つ選び、dp[{i}][v]=0 と初期化します。それ以外は十分大きい値(∞)とします。
その後、S を小さい順(ビット表現の昇順)に見ていき、各 S について以下の更新を順に行います。
- S を空でない真部分集合 A,S∖A の 2 つに分割し v で合体する。
dp[S][v]=∅=A⊊Smin(dp[A][v]+dp[S∖A][v]−c(v))
- マス v に対し、v と隣り合うマス u を以下で更新する。
dp[S][u]←min(dp[S][u], dp[S][v]+c(u))
これは最短経路問題と同じ形なので、すべての v の dp[S][v] を初期距離として Dijkstra 法で処理できます。このとき、
S=∅min(vmindp[S][v]+(S に含まれない島の面積の合計))
が求める答えとなります。計算量は O(3KHW+2KHWlog(HW)) です。