[BOJ]11052購入カード

4035 ワード
algorithm DP テキストリンク
📃 購入カード 
import sys
input = sys.stdin.readline 

n = int(input())
p = [0]+list(map(int, input().split()))
# max_prices = p 하면, 복사가 아니라 참조가 되어
# 한 곳을 변경하면 다른 곳도 똑같이 변경된다.
# (이 코드에서는 참조로 해도 이상은 없음.)
max_prices = p[:]

for i in range(2, n + 1):
    for j in range(1, i // 2 + 1):
        if max_prices[i] < max_prices[i - j] + max_prices[j]:
            max_prices[i] = max_prices[i - j] + max_prices[j]

print(max_prices[n])

に答える


動的プログラミングの問題を解決するには,まず基本点火関係を明らかにし,次に効率を向上させることができるスキームを考慮する.
一度にn枚のカードを購入する価格はprice(n)です.
n枚のカードを購入する際の最大金額をmax price(n)と呼びます.
ではmax price(n)は
price(n)
max_price(n - 1) + max_price(1)
max_price(n - 2) + max_price(2)
...
max price(n-k)+max price(k)の最大値に等しい.
[158]ジョセフス問題|白駿銀色4
HTML/CSSのWebアクセスのための寸法