货币系统
题目要求
题目描述：
给你一个 n 种面值的货币系统，求组成面值为 m 的货币有多少种方案。
输入格式：
第一行，包含两个整数 n 和 m 。
接下来 n 行，每行包含一个整数，表示一种货币的面值。
输出格式：
共一行，包含一个整数，表示方案数。
数据范围：
n≤15,m≤3000
输入样例：
3 10 1 2 5
输出样例：
10
思路分析
f[i]代表恰好用了 i元钱的时候的方案数，注意本题会爆 i n t，需要开longlong
代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const int N = 3010; LL f[N]; int main() { int n, m; cin >> n >> m; f[0] = 1; for (int i = 1; i <= n; i ++ ) { int w; cin >> w; for (int j = w; j <= m; j ++ ) f[j] += f[j - w]; } cout << f[m] << endl; return 0; }
货币系统
题目要求
题目描述：
输入格式：
输出格式：
输出文件共有 T 行，对于每组数据，输出一行一个正整数，表示所有与 ( n , a )等价的货币系统 ( m , b ) 中，最小的 m 。
数据范围：
1≤n≤100,
1≤a[i]≤25000,
1≤T≤20
输入样例：
2 4 3 19 10 6 5 11 29 13 19 17
输出样例：
2 5
思路分析
代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 25010; int w[N]; int f[N]; int main() { int T; cin >> T; while (T -- ) { int n; cin >> n; for (int i = 1; i <= n; i ++ ) cin >> w[i]; sort(w + 1, w + n + 1); memset(f, 0, sizeof f); f[0] = 1; int m = w[n]; int res = 0; for (int i = 1; i <= n; i ++ ) { if (!f[w[i]]) res ++; for (int j = w[i]; j <= m; j ++ ) f[j] += f[j - w[i]]; } cout << res << endl; } return 0; }
