题解：洛谷 P1474 [USACO2.3] Money System / [USACO07OCT] Cow Cash G

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1474 [USACO2.3] Money System / [USACO07OCT] Cow Cash G - 洛谷【题目描述】母牛们不但创建了它们自己的政党而且选择了建立了自己的货币系统。由于它们特殊的思考方式它们对货币的数值感到好奇。传统地一个货币系统是由1 , 5 , 10 , 20 , 25 , 50 , 100 1,5,10,20,25,50,1001,5,10,20,25,50,100的单位面值组成的。母牛们想知道有多少种不同的方案来用货币系统中的货币来构造一个确定的面值。举例来说使用一个由1 , 2 , 5 , 10 1,2,5,101,2,5,10的单位面值组成的货币系统产生18 1818面值的一些可能的方法是18 × 1 18 \times 118×19 × 2 9 \times 29×28 × 2 2 × 1 8 \times 22 \times 18×22×13 × 5 2 1 3 \times 5213×521等等。写一个程序来计算有多少种方法用给定的货币系统来构造一定数量的面值。保证总数在64 6464位带符号整数的范围内。【输入】第一行两个整数代表货币系统中货币的种类数目V VV1 ≤ V ≤ 25 1 \leq V \leq 251≤V≤25和要构造的面值N NN1 ≤ N ≤ 10 , 000 1 \leq N \leq 10,0001≤N≤10,000。第二行V VV个整数代表所有货币的单位面值。【输出】仅一行一个整数代表方案数。【输入样例】3 10 1 2 5【输出样例】10【算法标签】#普及【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN30,M10005;// 定义最大物品数N和最大金额Mintn,m;// 物品数量n目标金额minta[N];// 存储每个物品的金额intdp[M];// 动态规划数组dp[j]表示金额j的组成方案数signedmain()// 主函数{cinnm;// 输入物品数量和目标金额for(inti1;in;i)// 遍历所有物品{cina[i];// 输入第i个物品的金额}dp[0]1;// 初始化金额为0的方案数为1不选任何物品for(inti1;in;i)// 遍历每个物品{for(intja[i];jm;j)// 遍历所有可能的目标金额{dp[j]dp[j-a[i]];// 状态转移方程将当前物品加入金额j-a[i]的方案中}}coutdp[m];// 输出组成目标金额m的方案数return0;// 程序正常结束}【运行结果】3 10 1 2 5 10