[BOJ 11052]購入カード(Python)

7470 ワード
白駿 DP テキストリンク

質問する


https://www.acmicpc.net/problem/11052

これはn枚のカードを購入する際、最も高い購入金額の問題です.

問題を解く

dp[i]=1つのカードを購入したときに持つことができる金額の最大値
まず,nが3未満のときに値を定義した.
dp[1] = p[1]
dp[2] = max(dp[1]*2, p[2])
nが3より大きいことから、点火式で値を求める.
for i in range(3,n+1):
    for j in range(1,i+1):
        dp[i] = max(p[i], dp[i], dp[j] + dp[i-j])
  • p[i]:i個のカードを含むパッケージ金額다른 카드팩과 섞어 구매하는 것보다 단일 카드팩의 금액이 가장 비쌀 수 있다.
  • dp[i] : 이미 구해진 최댓값이 다른 값으로 덮어씌워질 수 있다.
  • dp[j]+dp[i-j]:他のカードパッケージとの混合購入で得られる最大金額
    • .

    コード#コード#

    import sys
input = sys.stdin.readline

n = int(input())
p = ['dummy'] + list(map(int,input().rsplit()))

# dp[i] = 카드 i개를 구매할 때 가질 수 있는 금액의 최댓값
dp = [0] * (n+1)
dp[1] = p[1]
dp[2] = max(dp[1]*2, p[2])

for i in range(3,n+1):
    for j in range(1,i+1):
        dp[i] = max(p[i], dp[i], dp[j] + dp[i-j])

print(dp[n])
    2021年8月20日39日目
    単純なボリュームコード符号化プログラム