http://yukicoder.me/problems/896
- まず、union-findで島の大きさを列挙し、その列挙されたものに対し、bag[0]=-1として、最小値版0-1ナップザックを行えばよいです。
- しかし、これでは、島の個数をXとすると、O(NX)であり、Xの最大値はNなので、島が多数あった場合に最悪O(N2)となり、TLEになってしまいます。
そこで、ダブリングを行います。例えば、大きさ2の島が10個ある場合、「大きさ2コスト1」を10回並べるのではなく、「大きさ2コスト1」「大きさ4コスト2」「大きさ8コスト4」「大きさ6コスト3」の4つを並べれば良いことになります。
- 最後の3は
10-1-2-4のように求められます。
- 最後の3は
この考え方はtails氏の答案( http://yukicoder.me/submissions/64600 )を参考にしました。ありがとうございます。
追伸
- 蟻本302ページに普通に書いてありました。まだ読み終わっていないため、勉強不足ということが露呈しました…
- deque解法が多いのはスライド最小値の考え方で解けるかららしいですね。ダブリング解法は(計算量が少し増えることもあって)少数派のようです。