526互联

1021. 货币系统

发布时间 2023-03-30 15:30:51作者: zhangk1988

题目描述

有n中面值的货币，每种有无限个，问组成m的方案总数？

f1-xxx

完全背包求方案数

  1. 完全背包裸题

代码

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int MAX_M = 3000;
LL f[MAX_M + 10];

int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    f[0] = 1;
    
    while (n--)
    {
        int v;
        scanf("%d", &v);
        
        for (int j=v; j <= m; j ++)
            f[j] += f[j - v];
    }
    
    printf("%lld", f[m]);
    
    return 0;
}

总结

  1. 注意求和会爆int，定义方案数组以及打印的时候对long long 怎么处理