[BOJ]購入カード(no.1102)

質問する

最近、ミンギュ家の近くではスターリンクから作られたPSカードの収集が流行している.
PSカードはPS分野の有名人の身分証明書です.カード1枚につき表示レベルの色が塗られており、以下の8種類があります.
伝説カード
レッドカード
オレンジカード
磁気カード
ブルーカード
グリーンカード
グリーンカード
グレーカード
カードはパッケージ形式でしか購入できません.パッケージの種類は1つのパッケージ、2つのパッケージ、...N個のカードを含むカードパックはN種類あります.
ミンギュ氏は、クレジットカードの数が少ないクレジットカードでも、価格が高ければ、高いレベルのクレジットカードがたくさんあると信じている.そのため、ミンギュはできるだけ多くのお金を払ってN枚のカードを買いたいと思っています.i枚のカードを含むパッケージの価格はPi元です.
例えば、P 1=1、P 2=5、P 3=6、P 4=7の4種類がある場合、ミンギュが4枚のクレジットカードを持つために支払った金額の最高値は10元である.2回に2つ入ったカードバッグを買えばいいです.
P 1=5、P 2=2、P 3=8、P 4=10の場合、1枚のカードが入ったカードパックを4回買うと20元になります.
最後に、P 1=3、P 2=5、P 3=15、P 4=16の場合、3つのカードパックと1つのカードパックを購入して18元を支払うのが最低価格です.
クレジットカードパックの価格を渡した場合、N枚のクレジットカードを購入するために、ミンギュが支払った金額の最低価格を求めるプログラムを作ってください.N枚以上のカードを買って、残りのカードを捨ててN枚にするのは不可能です.つまり、購入したカードパックに含まれるカード数の和はNに等しくなければならない.

入力

1行目はミンギュが購入するカードの個数Nを与える.(1 ≤ N ≤ 1,000)
2行目はP 1からPNまでPiの順に与えられる.(1 ≤ Pi ≤ 10,000)

しゅつりょく

1行目にミンギュがN枚のカードを持つために支払った金額の最高額がプリントアウトされる.

🤔 の意見を打診

を要約すると、n枚のカードを買うときの最高価格を求めます.(最終的には重複組合せの問題です.)

注釈

dp[i]:カード数がiの場合の最大金額

ヶーシング

最後に、整数がnである場合、与えられたPのすべての数は、前の数であってもよい.
つまり.
dp[n-1] + p[1],
dp[n-2] + p[2],
dp[n-3] + p[3],
...
dp[n-n] + p[n]
の中で一番値打ちがある.
🔥 てんかしき
-dp[i]=dp[i-k]+p[k]の最値
あるいは
-p[i]=p[i-k]+p[k]の最値
2つ目の点火式の観点は少し違いますが、
数量がNの場合∑ i일 때 최댓값 + N-i일 때 최댓값 (i=1...N)同一とみなす.
一つ目は本当に最後の数字がどのように決まるかに焦点を当てているとしか言いようがありません.△これは確かに正石に似ている.
個人的には最初の方が簡単だと思います
2つ目の方法は、入力配列を再使用するため、メモリをさらに最適化できます.

📌 説明する

import sys
input = sys.stdin.readline

N = int(input())
p = [0] + list(map(int, input().split()))

for i in range(1,N+1):
    p[i] = max(p[j] + p[i-j] for j in range(i//2, i+1))

print(p[N])

レビュー

第二次点火式は分かりにくいですが、解けるとそんなに簡単ではありません...

は解けましたが、まだまだ足りない感じです.

コードにダイヤルする前に、ケースが完全に割り当てられているかどうかを考慮します.