[21512][伯俊/BOJ]購入161994号カード2
1005 ワード
質問する
にゅうしゅつりょく
に答える
白準11052カードを購入する問題は最大値を求めることです.
白準161994カード2を購入するのは最小値を求める問題です.
カードを解く場合、簡単にmaxをminに変更すれば問題が解決すると思ったのですが、結果値は0です.
これは、d配列がグローバル変数として宣言され、初期値が0であるためである.
この状態で、最小値minで最小値を検索しようとすると、0が最小値であるため、0が出力される.
したがって、d[1]=A[1]のみを初期化するのではなく、d[1]からd[n]までをそれぞれA[1]~A[n]に初期化すれば問題を解決できる.
コード#コード#
#include <bits/stdc++.h>
using namespace std;
int d[100002];
int A[100002];
int dp(int n)
{
for (int i = 1; i <= n; ++i)
d[i] = A[i];
for (int i = 2; i <= n; ++i)
for (int j = 1; j <= i; ++j)
d[i] = min(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
この問題について([21512][伯俊/BOJ]購入161994号カード2), 我々は、より多くの情報をここで見つけました https://velog.io/@kwkim95/210508백준BOJ-16194번-카드-구매하기-2テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol