[21512][伯俊/BOJ]購入161994号カード2

質問する

にゅうしゅつりょく

に答える

白準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);
}