2/6 - TopCoderとJ言語と時々F#

一番遅い二人を向こう岸に運ぶことを考える。t[1]を最も速い人、t[n]を最も遅い人とする(tはソートされている)。このとき二種類の方法が考えられる。

1. (1, 2)で行く→1が帰ってくる→(n-1, n)で行く→2が帰ってくる
2. (1, n)で行く→1が帰ってくる→(1, n-1)で行く→1が帰ってくる

それぞれかかる時間は

1. t[2]+t[1]+t[n]+t[2] = t[1] + 2*t[2] + t[n]
2. t[n]+t[1]+t[n-1]+t[1] = 2*t[1] + t[n-1] + t[n]

ここで方法1が方法2より速い時の条件を考えると

t[1] + 2*t[2] + t[n] < 2*t[1] + t[n-1] + t[n]
2*t[2] - t[1] < t[n-1]

となる。つまり二番目に遅い人のかかる時間が大きければ方法1を、小さければ方法2を用いれば良い。

やるだけ。

dp[i][j] := i人選んでその和をjにできるか

でDP。n/2人選んで作ることのできる和をsとすると、2*s-合計が最も少なくなるようなsが答。

というかWaterloo local contest はナップサック的DPがお好きなんですかね。

やるだけ。

にぶまっちんぐ

やるだけ。