arc 105 c

問題

• 重さ$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なので大丈夫。