2365: 【入门】货币问题
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：5
解决：3
题目描述
某国家有 n 种不同面值的货币，第 i 种货币价值 ai 元。
请问：如果每种货币都提供任意多的数量的情况下，如果需要 m 元金额的货币，有多少种不同的方案？
输入
第一行两个整数 n，m（≤5000，n≤100)；
以下 n 行，每行一个整数，第 i+1 行为第 i 种货币的面值。
输出
一个整数，为方案数（方案数≤1018）。
样例输入 复制
3 10
1
2
5样例输出 复制
10提示
完全背包，硬币组合计数，每种硬币无限拿，凑 m 元，求组合方案数（不考虑顺序）。
注意：方案数最大可达\(10^{18}\)，要用
long long。
状态：dp[j] 凑出 j 元的方案数。
初始化：dp[0]=1，0 元有 1 种方案（什么都不选）。
完全背包正序循环体积。
关键点
-
数据范围大，必须用
long long，不能用 int。 -
完全背包，j 从
a到m正序遍历。 -
dp[0]=1是计数起点。 - 外层遍历硬币，内层遍历金额，保证不会出现顺序不同算不同方案的情况。
#include <iostream>
using namespace std;
typedef long long ll;
const int MAXM = 5005;
ll dp[MAXM];
int main()
{
int n, m;
cin >> n >> m;
dp[0] = 1;
for(int i = 1; i <= n; i++)
{
int a;
cin >> a;
//完全背包：正序
for(int j = a; j <= m; j++)
{
dp[j] += dp[j - a];
}
}
cout << dp[m] << endl;
return 0;
}