「条件を手で計算してみる大切さ」を教えてくれる問題です。
ソートしてからナップサックDPで解けます。
問題
種類の活動の中から つ以上を選び、好きな順序で行なう。
最初の体力は であり、活動 を行うと、得点 を得た後、体力が 減少する。
得られる得点の和の最大値を求めよ。
制約
考察
活動を行った時に得られる得点が「その時点の体力」に依存するので、そのままナップサックDPは使えません。
しかし、活動の順序を全検索( 通り)することは、時間的に不可能です。
ここで、活動 → 活動 を行った場合と、活動 → 活動 を行った場合の、それぞれ得られる得点を計算してみます。
体力の減少は、どちらも同じ です。
得られる得点の差は、
それで、
となります。ゆえに、 が大きい方から処理する(降順でソート)のが最善です。
実装例
INF = 10**10
N, H = map(int, input().split())
Activities = []
for i in range(N):
a, b = map(int, input().split())
Activities.append((a, b))
Activities.sort(key=lambda x: (x[0]/x[1]), reverse=True)
dp = [[-INF] * (H+1) for _ in range(N+1)]
dp[0][H] = 0
for i in range(N):
A, B = Activities[i]
for h in range(H+1):
dp[i+1][h] = max(dp[i+1][h], dp[i][h])
if h > 0:
h1 = max(h-B, 0)
dp[i+1][h1] = max(dp[i+1][h1], dp[i][h] + A*h)
print(max(dp[N]))
DP高速化
ここからは趣味の範囲です。
このコードで、PyPy で 336 ms でACできますが、さらに高速化できます。
は にしか依存しないので、 を管理するのではなく、(dp
とする) と (dp1
とする)の2つのみ管理するようにします。
ループごとに dp1
を dp
で更新し、ループの最後に dp
を dp1
に置き換えます。
dp = [-INF] * (H+1)
dp[H] = 0
for A, B in Activities:
dp1 = [-INF] * (H+1)
for h in range(H+1):
dp1[h] = max(dp1[h], dp[h])
if h > 0:
h1 = max(h-B, 0)
dp1[h1] = max(dp1[h1], dp[h] + A*h)
dp = dp1
print(max(dp))
これで、PyPy で 260 ms です。
さらに、配るDPの更新の時に大きい のみを更新しているので、 1本を で更新していけばOKです。
dp = [-INF] * (H+1)
dp[H] = 0
for A, B in Activities:
for h in range(H+1):
if h > 0:
h1 = max(h-B, 0)
dp[h1] = max(dp[h1], dp[h] + A*h)
print(max(dp))
これで、PyPy で 150 ms です。
ただし、これでもPythonではTLEします。
計算量 が なので、PyPyでないと時間が厳しいです。