白駿2293硬貨

質問する

質問リンク:https://www.acmicpc.net/problem/2293

ポリシー

題では、まず入力、出力を分析し、解答します.

の前に、カード、ブリッジの問題とアルゴリズムは似ています.例えば、価値の和は10元で、すべての種類の硬貨を検査しなければならない.

コード#コード#

#include<bits/stdc++.h>

using namespace std;



int main(){
    ios_base::sync_with_stdio(false);
    freopen("../input.txt","rt",stdin);
    
    int i, j, n, k;
    int dp[10001] = {0,};

    cin >> n >> k;

    int coins[n];

    for(i=0; i<n; i++) scanf("%d",&coins[i]);
    dp[0] = 1;

    for(i=0; i<n; i++){
        for(j=coins[i]; j<=k; j++){
            if(j-coins[i] >= 0){
                dp[j] += dp[j - coins[i]];
            }
        }
    }

    return 0;
}

感想

解決しなかったので、他の人のコードを見ました.この問題を見て、橋を架けたり、カードを使ったりする問題を復習します.