ABC219_D(Strange Lunchbox)
問題
考えたこと
- 全探索は無理。弁当を食べる場合、食べない場合の 2 択で考えると最大で
の計算量になってしまう。
- ナップザック問題の応用で行けそう、までは思いつく。
- DP[選択した荷物の数][たこ焼きの数][たい焼きの数] で管理...？
- 詰まる。
====ここまででコンテスト終了====
- 解説を見て次のように理解した。
- DP[弁当の番号][たこ焼きの数][たい焼きの数] = その重さになる弁当の個数の最小値 を保持しておく。
- DP のテーブルは十分に大きな数で初期化しておく。
- DP[0][0][0] = 何も弁当を食べていないのでたい焼きもたこ焼きも食べていない状態は 0 で初期化する。
- 弁当 1 を たこ焼き0, たい焼き0 の状態で食べる場合と食べない場合で判断する。
- 食べる場合: DP[1][0 + 弁当 1 のたこ焼きの数][0 + 弁当 1 のたい焼きの数] を更新する。
- 食べない場合: DP[1][0][0] を 更新する。
- 例えば弁当に入っているたこ焼きが 3 個、たい焼きが 2 個だったとすると弁当 1 を食べることによって DP[1][3][2] が 1 に更新される。
- この状態で弁当 2 (1, 3 とする)を食べることを選ぶ場合
- 弁当 1 を食べていなかった場合を仮定する場合には DP[2][1][3] = DP[1][0][0] + 1 で更新される。
- 弁当 1 を食べていたと仮定する場合には DP[2][4][5] = DP[1][3][2] + 1 で更新される。
今食べようとしている弁当、食べる/食べない場合のたこ焼きとたい焼きの数、その場合の合計弁当数を保持する。弁当数が一番小さいものを保持し続けていけば最終的に DP[最後の弁当][目標のたこ焼き数][目標のたい焼き数] が答えになる。なお、どこかの弁当を食べた結果、目標のたこ焼き数と目標のたい焼き数が X と Y を超えた場合には X と Y だとして扱ってしまう。別に超えても目標の個数が食べられていることには変わりがないため、そのように扱っても問題はない。
以下、実装。
N = int(input()) X, Y = [int(x) for x in input().split()] bento = [] for i in range(N+1): if i == 0: A, B = 0, 0 else: A, B = [int(x) for x in input().split()] bento.append((A, B)) dp = [[[10**9] * (Y+1) for x in range(X+1)] for y in range(N+1)] for i in range(N+1): A, B = bento[i] if i == 0: dp[i][0][0] = 0 else: for j in range(X+1): for k in range(Y+1): # 弁当を選択する場合 # 食べたあとの X, Y において弁当の個数が小さい方を残す ans = min(dp[i-1][j][k]+1, dp[i][min(j+A, X)][min(k+B, Y)]) dp[i][min(j+A, X)][min(k+B, Y)] = ans # 弁当を選択しない場合 # 前の値を引き継ぐのと、いまの値で弁当の個数が小さい方を残す dp[i][j][k] = min(dp[i-1][j][k], dp[i][j][k]) if dp[N][X][Y] == 10**9: print(-1) else: print(dp[N][X][Y])
