白駿9084硬貨

問題の説明

方法

コインタイプの代表的な問題は、適切な方法で最小限のコイン個数を近づけて製造することであるため、比較的馴染みのあるタイプの問題であるため、理解しやすい.しかし、今回の質問はコインの最小または最大構成タイプではなく、可能な限りの数を聞くことです.
初めて思ったのはDPN元の構成方法にはx種があると仮定し,M元のタイプを増やせばN+M元の構成方法はx種に維持できる.したがって,基本的な問題はDPに基づくサブ問題が重なって使用される核心思想にアクセスする.
ただし、問題が発生する可能性のある部分はN元を構成するため、N/4元硬貨(x)が4個ある場合、M元を追加する.N+M元がx 1+Myの形でも状況の数が現れるので、複雑な状況が発生します.
私はすでに問題の中で起こり得る複雑な状況を把握しているので、全体の方法に戻って、DPの中でもKnapsack方式で解くことができると思います.リュックサックに最大限入れられる個数のコンセプトに加え、コインできれいに値をつけるコンセプトを加えれば、適応しやすいように見えます.

// DP[i][j] i번째 동전까지 사용하여 j원을 구성할 수 있는 모든 경우의 수
DP[i][j] = DP[i-1][j-coin[i]]

次のようなアイデアを引き出すことができます.しかし、このように配置するとコインの種類が1つしかないと、値がどんどん大きくなるという問題があり、1つのコインしかない場合は、それを1つのコインしかない種類に変えて、さらに値を処分して、以前のコインまで使っていたら、数に基づいて現在追加できる場合があり、その値は更新方式であるため,2次元DPではなく1次元DPを2重複文に更新する方式が考えられる.

// 동전의 종류 한 가지면 나누어 떨어질때로 값 업데이트
if(i == 1){
	if(j % coin[i] == 0)
        dp[j]++;
}
// 동전의 종류가 두번째 이후이면 이전에 나온 경우의 수들을 바탕으로
// 내가 들어갈 수 있는 원이면 들어가면서 값 업데이트 
else{
	if(j>=coin[i])
    	dp[j] += dp[j-coin[i]];
}

j円玉[i]よりも円が大きく、何度も繰り返し入れられる場合、下から1つずつ埋まっていくと、以前の場合、コイン[i]円は何度入れられるかというコンセプト.
ex)6元、コイン={1,2}
iが1の場合の実行結果
({1}) ({12}) ({13}) ({14}) ({15}) ({1*6})
iが2の場合の実行結果
({1}) => 1
({12}, {2}), ({13}, {2, 1}) => 2
({14}, {21, 12}, {22}), ({15}, {21, 13}, {22, 11}) =>3
({16}, {21, 14}, {22, 12}, {2*3}) => 4
このように、新たに追加された硬貨を加える回数が増えると状況の数に差が出てくるので、j元にはj-cong[i]元に1を足すだけでよい.
###C++コード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair <ll, ll>;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  //freopen("inp.txt", "r", stdin);
  
  int T;
  cin >> T;
  while(T--){
    int N, M;
    cin >> N;
    vector<int> coin(N+1);
    for(int i=1; i<=N; i++)
      cin >> coin[i];
    cin >> M;
    
    vector<int> dp(M+1, 0);
    dp[0] = 1;
    for(int i=1; i<=N; i++){
      for(int j=1; j<=M; j++){
        
        // 동전 종류가 하나일 경우
        // 나누어 떨어지는 경우만 1가지로 카운트
        if(i == 1){
          if(j % coin[i] == 0)
            dp[j]++;
        }
        
        // 동전 종류가 여러가지일 경우
        // 동전보다 만들어야 하는 돈의 크기가 크면
        // 기존에 만들어진 조합에 자기만 추가하면 되므로 이전값에 자기만 추가
        else{
          if(j>=coin[i])
            dp[j] += dp[j-coin[i]];
        }
      }
    }
    cout << dp[M] << '\n';
  }

}