JOI難易度6 IOI饅頭
問題原文
問題要旨
価値がそれぞれ であるような饅頭が、 個と、饅頭を入れるための箱が 個ある。
番目の箱は、饅頭を [C_j] 個入れられるが、コストが かかる。
箱に詰めた饅頭の価値の総和 - 箱のコストを最大化せよ。
解法
饅頭は明らかに価値の高いものから入れるのが最適。饅頭を 個入れられる時の合計価値は累積和をとっておけば高速に求められる。
次に、「饅頭を 個入れると決めた時」に、そのための箱を準備する最小コストが欲しくなるが、これはナップサックDPの要領で簡単に求められる。
あとは饅頭を入れる個数全てについて、前計算しておいたものを使って答えを計算していけばいい。
必ずしも箱の要領ぴったりに饅頭を詰める必要はないことに少し注意すること。(価値が1000円の饅頭が1個だけ、 100個入る箱が1円で1個だけ、のような時に困る)
実装
ちょっとTLが怖かったのでDPテーブルは一次元で持っている。
更新は後ろからやる必要がある。ちなみにPyPy3で400ms切ってました(杞憂だった)
import sys from itertools import accumulate M, N = map(int, input().split()) Buns = [int(sys.stdin.readline()) for _ in range(M)] Boxes = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # 累積和を取る M += 1 Buns = [0] + sorted(Buns, reverse=True) Buns = list(accumulate(Buns)) # dp[i] := i個饅頭を入れるための最小コスト dp = [float('inf')] * M dp[0] = 0 for c, e in Boxes: for i in reversed(range(M)): to = i + c if i + c < M else M - 1 dp[to] = min(dp[to], dp[i] + e) ans = 0 for i in range(M): ans = max(ans, Buns[i] - dp[i]) print(ans)
感想
ド典型だけど、DPをさくっと倒せると少し誇らしい気持ちになる(えっへん)