[伯俊/python 3を購入]11052カード
https://www.acmicpc.net/problem/11052
これはダイナミックプランニングを利用して解決される問題です.
n枚のカードが支払う最高価格.
に答える
これはダイナミックプランニングを利用して解決される問題です.
n枚のカードが支払う最高価格.
dp[n] = max(P[n], dp[1] + P[n-1], dp[2] + P[n-2], ... , dp[n-1] + P[1])で表すことができます.これをコードで実装して解決します.コード#コード#
# Initial
N = int(input())
P = list(map(int, input().split()))
P.insert(0, 0) # 인덱스 맞추기용
dp = [0 for _ in range(N+1)]
answer = 0
# P[n] = 카드 n개가 포함된 카드팩의 가격
# Make DP table
dp[1] = P[1]
for i in range(1, N+1):
temp = 0
for j in range(1, i):
temp = max(temp, dp[i-j] + P[j])
dp[i] = max(temp, P[i])
# Answer
answer = dp[N]
print(answer)Reference
この問題について([伯俊/python 3を購入]11052カード), 我々は、より多くの情報をここで見つけました https://velog.io/@nyamnyam/백준Python3-11052-카드-구매하기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol