货币系统
发布时间
阅读量：
阅读量
货币系统
Description
给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。
Input
第一行，n和m，表示面值种数n和组成的面值m。
接下来n个整数，代表n种面值。
Output
输出方案数。
Sample Input
3 10
1 2 5
Sample Output
10
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAX_M=1e4+5;
const int MAX_N=30;
ll dp[MAX_M];
int main(){
int n,m,a[MAX_N];
while(scanf("%d%d",&n,&m)!=EOF){
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
dp[0]=1;
for(int i=1;i<=n;i++)
for(int j=a[i];j<=m;j++)
//状态转移方程
dp[j]=dp[j]+dp[j-a[i]];
printf("%lld\n",dp[m]);
}
return 0;
}全部评论 (0)
还没有任何评论哟~