きろく

特筆すべき記録のまとめ

AtCoder Beginner Contest 145:E - All-you-can-eat

問題

https://atcoder.jp/contests/abc145/tasks/abc145_e

解法

まず,食べることにした料理の中では食べるのに必要な時間が短い順に注文するのが最適なので,料理を食べるのに必要な時間が短い順にソートしておく.ここで以下の DP を考える.

dp(i, j) := 時刻が j のとき,i 番目の料理以降で得られるおいしさの和の最大値

遷移は i 番目の料理を食べるか,食べないかの 2 通りであるから,

dp(i, j) = max(dp(i + 1, j + A_i) + B_i, dp(i + 1, j))

となる.O(NT).

解答

https://atcoder.jp/contests/abc145/submissions/9001181

f:id:babcs2035:20191218152339p:plain