给你一个\(n\)种面值的货币系统,求组成面值为m的货币有多少种方案。
其中\(1 \le n\),\(m \le 10000\)
输入
第1行:两个数\(n\)(表示面值的种数) ,\(m\)(表示\(n\)种面值组成的总面值)
接下来\(n\)行,每行一个数,表示一种面值
输出
\(n\)种面值组成面值为\(m\)的货币的方案数。
样例
样例输入1
3 10
1
2
5
样例输出1
10
代码
#include <bits/stdc++.h>
using namespace std;
int val[25];
long long dp[10008];
int main()
{
int m,n,cnt=0;
cin >> n >> m;
for(int i=1;i<=n;i++)
{
cin >> val[i];
}
dp[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=val[i];j<=m;j++)
{
dp[j]+=dp[j-val[i]];
}
}
cout << dp[m];
return 0;
}
标签:le,val,int,样例,系统,货币,面值
From: https://www.cnblogs.com/momotrace/p/monetary-system.html