[21508][伯俊/BOJ]11052号カードを購入
1154 ワード
質問する
にゅうしゅつりょく
に答える
ミンギュはN枚のカードを買う.
1からNまでカードが存在し、pは各カードの値である.カード購入に必要な最大値の問題です.
4枚のカードがある場合、これらのカードを購入する最大値は次のとおりです.
カード.
カード3+カード1
カード2+カード2
カード1+カード3
全部で4つのケースが存在します.
次のコードに実装します.
D[4] = D[4]
D[4] = D[3] + A[1]
D[4] = D[2] + A[2]
D[4] = D[1] + A[3] for (int i = 2; i <= n; ++i)
for (int j = 1; j <= i; ++j)
d[i] = max(d[i], d[i - j] + A[j]);コード#コード#
#include <bits/stdc++.h>
using namespace std;
int d[100002];
int A[100002];
int dp(int n)
{
d[1] = A[1];
for (int i = 2; i <= n; ++i)
for (int j = 1; j <= i; ++j)
d[i] = max(d[i], d[i - j] + A[j]);
return d[n];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> A[i];
cout << dp(n);
}Reference
この問題について([21508][伯俊/BOJ]11052号カードを購入), 我々は、より多くの情報をここで見つけました https://velog.io/@kwkim95/210508백준BOJ-11052번-카드-구매하기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol