「条件を手で計算してみる大切さ」を教えてくれる問題です。 ソートしてからナップサック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でないと時間が厳しいです。