[Python] ABC015 D DP 100点

[Python] ABC015 D メモ化再帰 100点

問題 D – 高橋くんの苦悩 回答 defaultdict defaultdict を使ってみましたが、残念ながらＴＬＥでした。 import collections W = int(input()) N, K = map(int, ...

yottagin.com

2019-12-15 11:10

問題

D – 高橋くんの苦悩

回答

動的計画法を使います。

Python では TLE ですが、PyPy では間に合いました。

W = int(input())
N, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

dp = [[[0]*(W+1) for _ in range(K+1)] for _ in range(N+1)]

for n in range(N):
    for k in range(K+1):
        for w in range(W+1):
            a = AB[n][0] # 幅
            b = AB[n][1] # 重要度
            if w-a>=0 and k-1>=0:
                dp[n+1][k][w] = max(dp[n][k][w], dp[n][k-1][w-a]+b)
            else:
                dp[n+1][k][w] = dp[n][k][w]

print(dp[N][K][W])