外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

解説

E - Desire for Cat Food

作成者 nekooooooo、siooisi、jammy、trueryob

テスター jammy、siooisi、tau0529、trueryob

配点 300 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

解説

2次元のDP を用いることで高速に求められます。

以下では猫缶を 00 番目から N−1N-1 番目と数えます(問題文の ii 番目の猫缶を i−1i-1 番目と呼びます)。

dp[i][c]\mathrm{dp}[i][c] を「00 番目から ii 番目までの猫缶からいくつか選び、価格の合計がちょうど cc 円になるときの、大きさの合計の最大値」とします。そのような選び方がないときは −∞-\infty とします。

初期化

00 番目の猫缶を買わない場合と買う場合を入れます。

dp[0][0]=0,dp[0][K0]=V0\mathrm{dp}[0][0] = 0, \quad \mathrm{dp}[0][K_0] = V_0

ただし K0>MK_0 > M のときは買えないので、dp[0][K0]\mathrm{dp}[0][K_0] は入れません。それ以外は −∞-\infty とします。

遷移

0≤i≤N−2, 0≤c≤M0 \le i \le N-2,\ 0 \le c \le M について、dp[i][c]\mathrm{dp}[i][c] が −∞-\infty でなければ、次の 2 つの更新を行います。

i+1i+1 番目の猫缶を買わない場合

dp[i+1][c]←max⁡(dp[i+1][c], dp[i][c])\mathrm{dp}[i+1][c] \leftarrow \max\left( \mathrm{dp}[i+1][c],\ \mathrm{dp}[i][c] \right)

i+1i+1 番目の猫缶を買う場合(c+Ki+1≤Mc + K_{i+1} \le M のときだけ)

dp[i+1][c+Ki+1]←max⁡(dp[i+1][c+Ki+1], dp[i][c]+Vi+1)\mathrm{dp}[i+1][c + K_{i+1}] \leftarrow \max\left( \mathrm{dp}[i+1][c + K_{i+1}],\ \mathrm{dp}[i][c] + V_{i+1} \right)

max⁡0≤c≤Mdp[N−1][c]\max_{0 \le c \le M} \mathrm{dp}[N-1][c]

が最終的な答えになります。

計算量は O(NM)O(NM) です。

M, N = map(int, input().split())
K = []
V = []
for i in range(N):
    k, v = map(int, input().split())
    K.append(k)
    V.append(v)

NEG = float('-inf')

# dp[i][c] = 0 番目から i 番目までの猫缶から選び、価格の合計がちょうど c 円のときの大きさの合計の最大値
dp = [[NEG] * (M + 1) for _ in range(N)]
dp[0][0] = 0
if K[0] <= M:
    dp[0][K[0]] = max(dp[0][K[0]], V[0])

for i in range(N - 1):
    for c in range(M + 1):
        if dp[i][c] == NEG:
            continue

        # 買わない場合
        dp[i + 1][c] = max(dp[i + 1][c], dp[i][c])

        # 買う場合
        if c + K[i + 1] <= M:
            dp[i + 1][c + K[i + 1]] = max(dp[i + 1][c + K[i + 1]], dp[i][c] + V[i + 1])

print(max(dp[N - 1]))


ユーザー解説

ユーザー解説を書く

ユーザー解説はまだありません。