解説と異なる解法でした。
問題リンク
問題概要
平面上にN個の集落があり、各集落iは座標\( (X_i,Y_i) \)にあって重み\(P_i\)が与えられている。
また、X軸とY軸には線路がある。
この時、X軸またはY軸に平行な線路をK本追加して、「重み×最も近い線路までの距離」の和Sを最小化したい。
最小値を\(K=0...N\)まで求めよ。
解法
線路は集落を通るように敷くのが最適なので、候補は実質2N本しかない。
片方の向きの敷き方を固定して、もう片方の向きの線路の敷き方はDPする。
集落はX座標の昇順にソートしておく。
X軸に平行な線路( \(y=Y_i\) )の敷き方を1つ決め打ちし、最初に敷いてしまう。
この時点での距離の最小値を各集落に対しまず求めておく。
次にY軸に平行な線路( \(x=X_i \) )の敷き方に関してDPを行う。
\(dp[i][j][k]\) = (i番目の集落まで見て、最後に敷いた線路が集落jを通り、既に線路をk本敷いている時の集落jまでのSの最小値)
とする。(ただしj=0は線路を敷いていないとする)
この時\(j < i\)ならば
\(dp[i][j][k] = dp[i-1][j][k]\)
である。
また新たに集落iを通る線路を敷く事を考えると
\(dp[i][i][k+1] = min \{0 \leq j \leq i-1 | dp[i-1][j][k] + \sum_{l = j+1}^{i-1} P_l \times (集落lの距離) \} \)
となり、集落lの距離は前計算した物と集落j,iを通るものだけを考えれば良い。
\( dp[N][j][k] + \sum_{l = j+1}^{N} P_l \times (集落lの距離) \)
の最小値がこの場合での本数kでのSの最小値になる。
これを\(y=Y_i\)の敷き方\(2^N\)通り全てに対し試せばよい。
計算量は\(O(2^N N^4)\)になる。
定数は軽いが906msだったので結構危ない。
(7/26 追記：Σの部分を使いまわしたら普通にループが一個外せた。\(O(2^N N^3)\) で624ms。)
提出
https://atcoder.jp/contests/m-solutions2020/submissions/15448869
https://atcoder.jp/contests/m-solutions2020/submissions/15460557(7/26 追記)
感想
Nが小さいせいで色々解法が浮かぶのでかえって方針に悩んだ。
解説の方法は「\(3^N N^2\)だしなぁ」と思って切り捨ててしまった。
