[伯俊/python 3を購入]11052カード

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

に答える

これはダイナミックプランニングを利用して解決される問題です.
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)