怎么用ps做网站上的产品图,wordpress自定义文章类型分类模板,广东省网站建设网站,宁波网站建设服务宣传一下算法提高课整理 —
CSDN个人主页#xff1a;更好的阅读体验 — 本题链接#xff08;AcWing#xff09;
点这里
题目描述
给你一个n种面值的货币系统#xff0c;求组成面值为m的货币有多少种方案。
输入格式
第一行#xff0c;包含两个整数n和m。
接…宣传一下算法提高课整理 —
CSDN个人主页更好的阅读体验 — 本题链接AcWing
点这里
题目描述
给你一个n种面值的货币系统求组成面值为m的货币有多少种方案。
输入格式
第一行包含两个整数n和m。
接下来n行每行包含一个整数表示一种货币的面值。
输出格式
共一行包含一个整数表示方案数。
数据范围 n ≤ 15 , m ≤ 3000 n \le 15, m \le 3000 n≤15,m≤3000
输入样例
3 10
1
2
5输出样例
10思路
本题为DP问题可以使用闫氏DP分析法解题。
DP
将组成面值为 m m m 的货币看作背包容量 n n n 种价格的货币看做有该体积的物品状态计算 ······ f [ 0 ] ← 1 f[0] \leftarrow 1 f[0]←1 ······ f [ j ] ← f [ j − v ] f[j] \leftarrow f[j - v] f[j]←f[j−v]
注意要开 long long A C AC AC C o d e Code Code: C C C #include iostream
#include cstring
#include algorithmusing namespace std;typedef long long LL;const LL N 3010;LL n, m;
LL f[N];int main()
{scanf(%lld%lld, n, m);f[0] 1;LL v;for (LL i 1; i n; i ){scanf(%lld, v);for (LL j v; j m; j )f[j] f[j - v];}printf(%lld\n, f[m]);return 0;
}最后如果觉得对您有帮助的话点个赞再走吧
