問題

  • 重さ\(w_i, i=1,..,N\)のラクダが、橋を渡ろうとしている。
  • 橋は\(M\)個の部材からなり、\(j\)番目の部材は長さ\(l_j\)で耐加重が\(v_j\)である
  • ラクダは1列に並んで橋を渡る。ラクダ間の距離は場所によって異なってよいが、一定に保たれる
  • ラクダの列のを最短にせよ

ポイント1

まずは、ラクダの順列を固定して考える。このとき、各\(1 \le i < j \le N\)に対して、\(w_i + .. + w_j\)より 耐加重が小さい部材の最大長を\(L_{i,j}\)とすると、ラクダ\(i,j\)間の距離は\(L_{i,j}\)以上である必要がある。 \(L_{i,j}\)は、\(v_j\)をソートしておけば、各\(i,j\)に対して\(O(\log M)\)で計算可能。 \(L_{i,j}\)の計算は、全体として\(O(N^2 \log M)\)かかる。

ポイント2

頂点\(i\)から\(j\)に長さ\(L_{i,j}\)の有効辺を貼る。頂点\(1\)から\(N\)への最長路が求める最適値となる。 頂点\(1\)から頂点\(j\)への最長路の長さは、\(\max\{ 1 \rightarrow iの最長路 + i \rightarrow jの長さ \}\)

これは、DPで\(O(N^2)\)で計算可能。

これを、全順列について計算すれば良い。\(N\)は最大8なので大丈夫。