PKU 2573 一番遅い二人を向こう岸に運ぶことを考える。t[1]を最も速い人、t[n]を最も遅い人とする(tはソートされている)。このとき二種類の方法が考えられる。1. (1, 2)で行く→1が帰ってくる→(n-1, n)で行く→2が帰ってくる 2. (1, n)で行く→1が帰ってくる→(1…

PKU 2465 dp[i][j] := i番目のガソリンスタンドに居て、残り燃料jの時の最小の支払額としてDP。 PKU 2466 まず求めたい数列を a、入力の数列を s とする。ただし両方ソート済み。そうするとまずs[0] = a[0]+a[1] s[1] = a[0]+a[2]は明らか。ここで、あるiに…