当前位置:首页 > NOIP > 正文

信息学一本通-1273:【例9.17】货币系统

给你一个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;
    
}


更新时间 2019-03-22

有话要说...