白駿2294号:コイン2

9462 ワード
ps DP cpp テキストリンク

銅貨


白駿2294号:コイン2

アイデア


この金額を作るのに必要なコインの最低個数をDpテーブルに記録します.1番硬貨からN番硬貨までの金額をそれぞれS(1)~S(N)と呼ぶと、N個目の硬貨を用いてK元を作製するのに必要な最小硬貨個数は、N−1個目の硬貨を用いてK元を作製する場合の数と、N個目の硬貨を用いてK−S(N)元を作製する場合の数に1を加えた値(K−S(N)元、さらにS(N)元硬貨を1個使用すればよい)のうちより小さい場合である.

コード#コード#

#include <bits/stdc++.h>

using namespace std;

int arr[101][10001];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    queue<int> q;
    int n, k;
    cin >> n >> k;
    while (n--) {
        int x;
        cin >> x;
        q.push(x);
    }
    
    fill(&(arr[0][0]), &(arr[0][0])+101*10001, 100000);
    
    for (int i = 0; i < 101; i++) {
        arr[i][0] = 0;
    }
    
    int t, s = 1;
    while (!q.empty()) {
        t = q.front();
        q.pop();
        for (int i = 1; i <= k; i++) {
            arr[s][i] = arr[s-1][i];
            if (i >= t) {
                arr[s][i] = min(arr[s][i], arr[s][i-t] + 1);
            }
        }
        s++;
    }
    
    if (arr[s-1][k] == 100000) cout << -1;
    else cout << arr[s-1][k];
   
    return 0;
}

おしゃべり


注意int範囲.INT MAXプラス1でINT MINになりました
INT MAXプラス1なぜINT MIN?もっと勉強しなさい.
また,アレイを初期化する場合,2次元アレイであるため,ポインタ演算が少し乱れている.気をつけて.
[全員のネットや画像で学ぶHTTP&Network]学習4週間
たんほうこうチェーンテーブルシミュレーション実装