ABC153-E_CrestedIbisvsMonsterをpythonで解いた（動的計画法）

問題

• ABC153-E_Crested Ibis vs Monster

ポイント

• i番目の魔法を使うと、モンスターの体力をAi減らすことができますが、トキの魔力をBi消耗します
• -> ナップサックの大きさが決まっている条件の元で、ものの大きさを考慮しつつものの価値の合計を最大化する
• -> ナップサック問題
  • 【通常のナップサック問題】
    • 更新式
      • i-1個目までで同じ体積の結果を流用 or
      • i-1個目までの結果にi個目を加えた結果を比較
    • dp[i][j] = max( dp[i-1][j], dp[i-1][j-(iの体積)] + iの価値)
    • -> iは確定なので、iの体積を引いた体積をi-1までの種類のアイテムで価値を最大化したやつにiの価値を足す
  • 今回は【個数制限なしナップサック問題】
    • • dp[i][j] = max( dp[i-1][j], dp[i][j-(iの体積)] + iの価値)
• 参考
  • https://slidesplayer.net/slide/11433604/

解法

h,n = map(int,input().split())
a_list = []
b_list = []
for i in range(n):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)

# i番目の魔法までを使って体力j減らすのに必要な魔力の最小値
dp=[[float('inf') for i in range(h+1)]for i in range(n+1)]
dp[0][0]=0

for i in range(1,n+1):
  for j in range(h+1):
    if j>=a_list[i-1]:
      ai=a_list[i-1]
      bi=b_list[i-1]
      dp[i][j]=min(dp[i][j-ai]+bi,dp[i-1][j])
    else:
      dp[i][j]=min(dp[i-1][j],b_list[i-1])
ans=dp[n][h]
print(ans)

感想

• DPに強くならねば。