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