AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。
出典：
AtCoder Beginner Contest 219 D – Strange Lunchbox
二次元配列をどんどん更新していくDP。遷移自体はそこまで複雑でもないので、落ち着いて考えれば解けると思う。
# AtCoder Beginner Contest 219 D - Strange Lunchbox
# https://atcoder.jp/contests/abc219/tasks/abc219_d
# tag: DP 高橋君
# 典型的な DP 問題。
# DP[i][j][k]:
# 今 i-1 個目の弁当を購入するかどうか検討しているとき、
# これまでにたこ焼き j 個とたい焼き k 個を入手するのに
# 必要な弁当の数の最小値。
# たこ焼き・たい焼きが(a, b)入っている弁当を
# 購入する場合は、
# DP[i+1][j+a][k+b] = min(DP[i+1][j+a][k+b], DP[i][j][k] + 1)
# ただし、j + a と k + b は上限 X, Y でキャップしてやる
# 必要がある。
# 購入しない場合は、
# DP[i+1][j][k] = min(DP[i+1][j][k], DP[i][j][k])
# 二次元配列を更新しながら、弁当を買う場合と買わない場合を
# 検討していくようなイメージ。
def main():
N = int(input())
X, Y = map(int, input().split())
boxes = [list(map(int, input().split())) for _ in range(N)]
dpt = [[[-1] * (Y+1) for _ in range(X+1)] for _ in range(N+1)]
dpt[0][0][0] = 0
for i, (a, b) in enumerate(boxes):
for j in range(X+1):
for k in range(Y+1):
if dpt[i][j][k] == -1:
continue
# 購入するとき
new_tak = min(X, j + a)
new_tai = min(Y, k + b)
if dpt[i+1][new_tak][new_tai] > dpt[i][j][k] + 1 or dpt[i+1][new_tak][new_tai] == -1:
dpt[i+1][new_tak][new_tai] = dpt[i][j][k] + 1
# 購入しない時
if dpt[i+1][j][k] > dpt[i][j][k] or dpt[i+1][j][k] == -1:
dpt[i+1][j][k] = dpt[i][j][k]
print(dpt[N][X][Y])
main()配列を使い回す場合は、以下のような書き方になる。
# 配列を使い回すDPは以下のような感じ。
# こちらの方が、使用メモリも速度も効率は良くなる。
def main():
N = int(input())
X, Y = map(int, input().split())
boxes = [list(map(int, input().split())) for _ in range(N)]
dpt = [[-1] * (Y+1) for _ in range(X+1)]
dpt[0][0] = 0
# 使い回す際は、後ろからループを回す。
# ちなみに前から回した場合は、同じものをいくつでも入手可能
# というパターンになる。
for a, b in boxes:
for tk in range(X, -1, -1):
for ti in range(Y, -1, -1):
if dpt[tk][ti] == -1:
continue
new_tk = min(X, tk + a)
new_ti = min(Y, ti + b)
if dpt[new_tk][new_ti] == -1 or dpt[new_tk][new_ti] > dpt[tk][ti] + 1:
dpt[new_tk][new_ti] = dpt[tk][ti] + 1
print(dpt[X][Y])
main()