1/26 PKU

3375 Network Connection

ネットワークインタフェースと、パソコンをつなぐ。それぞれは数直線上にある。すべてのパソコンをいずれかのインタフェースにつなぎたい。複数のパソコンにつながれるインタフェースがあってはいけない。ケーブル長の和を最小化せよ。

O(MN)のDPを、適当に改善してO(N^2)にする