\(O(3^N)\) 時間で解きます。

アプローチ

\(1\) つ以上の集落の組み合わせを選んだとき、それらの集落のために鉄道路線を建設することを考えます。

この鉄道路線を、選んだ集落すべてが直接利用するとしたときの歩行距離の最小値が計算できます。これを \(\text{step}[s]\) （ \(s\) は集落の組合せ）とします。

鉄道路線を \(K\) 本建設する場合は、集落を \(K\) 回に分けて選んでそれらのために鉄道路線を建設し、残った集落をはじめからあった鉄道路線に割り当てることで答えを計算できます。

(1) step[s] の計算

公式解説でも述べられた通り、鉄道路線を建設する座標はいずれかの集落に一致すると仮定してかまいません。この建設場所の候補は全探索し、最小値を採用して \(\text{step}[s]\) とします。

その位置に鉄道路線を建設したときに、ある集落の市民の歩行距離の合計を計算するのは簡単です。よって、集落の集合の小さい順に、それらの集落すべての市民の歩行距離の合計も \(O(2^N)\) 時間で計算できます。

よって、 \(\text{step}[s]\) は \(O(N2^N)\) 時間ですべて計算できます。

(2) 動的計画法の高速化

初期値として、集落の集合 \(s\) に対して、それらをすべてはじめからあった鉄道路線に集落を割り当てた場合の歩行距離の合計を求めます。これは、 (1) で使ったものと同様の手順で計算できます。

\(\text{step}[s]\) を利用して \(1\) つずつ鉄道路線を建設し、集落に割り当てていきます。割り当てる集落は残っている集落の空でない部分集合なので、考える集落が \(n\) 個ある場合はおよそ \(3^n\) 通りを走査して計算することになります。

この割り当てを \(N\) 回繰り返します。ただし、 \(1\) 回割り当てるときに、番号が最大の集落を必ず割り当てることを仮定してもよく、この場合鉄道路線を追加するごとに考慮すべき集落は \(1\) つずつ減ります。これを利用すると、全体の計算量が \(O(3^N)\) で抑えられます。

解答例

C++ 言語です。

#include <iostream>
#include <algorithm>
using namespace std;
using i64 = long long;
#define rep(i,n) for(i64 i=0; i<(i64)(n); i++)
template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; }

int N;
i64 X[15], Y[15], P[15];

i64 applyer[1<<15];
i64 dp[1<<15];

i64 ans[16];

int main() {
    cin >> N;
    rep(i,N) cin >> X[i] >> Y[i] >> P[i];

    // (1)

    rep(i,1<<N) applyer[i] = 1001001001001001;

    rep(i,15){
        dp[0] = 0;
        rep(j,N) rep(m,1<<j){
            dp[m|(1<<j)] = dp[m] + P[j] * abs(X[i] - X[j]);
        }
        rep(m,1<<N) chmin(applyer[m], dp[m]);
    }

    rep(i,15){
        dp[0] = 0;
        rep(j,N) rep(m,1<<j){
            dp[m|(1<<j)] = dp[m] + P[j] * abs(Y[i] - Y[j]);
        }
        rep(m,1<<N) chmin(applyer[m], dp[m]);
    }

    // (2)
    
    dp[0] = 0;
    rep(i,N) rep(b,1<<i) dp[b|(1<<i)] = dp[b] + min(abs(X[i]), abs(Y[i])) * P[i];
    reverse(dp, dp+(1<<N));

    ans[0] = dp[0];

    rep(d,N){
        rep(i,1<<(N-d)) for(int subi=i; subi>0; subi=(subi-1)&i){
            chmin(dp[i-subi], dp[i] + applyer[subi]);
        }
        ans[d+1] = dp[0];
    }

    rep(i,N+1) cout << ans[i] << '\n';
    cout << endl;

    return 0;
}

提出