给你一个n种面值的货币系统,求组成面值为m的货币有多少种方案。
#include<iostream> #include<cstdio> using namespace std; int a[10001],n,m; long long f[10005]; //注意long long int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } f[0]=1; for(int i=1;i<=n;i++) for(int j=m;j>=a[i];j--)//f[j]表示面值为j的方案最优解。 for(int k=1;k<=j/a[i];k++) f[j]+=f[j-k*a[i]]; cout<<f[m];//表示最优解。 return 0; }
有话要说...