JOI 参加記 (~本選編)
覚えているうちに急いで書いたので誤字脱字があるかもしれません。
一次予選去年本選に出てたので免除されてた。一応 3 回目だけ出た。
二次予選とりあえず A と B をすぐに解く。 C もちょっと実装が面倒だが 20 分弱で解いた。
D を見る。
まず dp[i][j] = i 番目までの取る荷物が確定していて、移動した総距離が j の時の価値の総和の最大値 とすると、区間 [i, j] 内での価値の上位 W 個の総和を O(N^3) で前計算すれば O(N^2D) になっ