P1474 Money System / Cow Cash G网页链接P1474 Money System / 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个整数代表所有货币的单位面值。输出格式仅一行一个整数代表方案数。输入输出样例 #1输入 #13 10 1 2 5输出 #110说明/提示翻译来自 NOCOW。USACO Training Section 2.3解题思路本题是完全背包求组合方案数的经典模板题核心是通过动态规划统计用无限枚指定面值货币凑出目标金额的总方案数且不计货币选取顺序。1. 问题建模每种货币可以无限次使用要求凑出总面值N求不同的组合方案数。由于选取顺序不同不算不同方案例如先选1再选2与先选2再选1视为同一种因此采用「外层枚举货币、内层枚举金额」的完全背包实现方式保证每种组合仅被计数一次避免重复统计排列。2. 动态规划设计状态定义f[j]表示凑出金额j的方案总数。初始边界f[0] 1凑出金额0的方案有且仅有1种不选取任何货币。状态转移对第i种面值为p[i]的货币有两种选择不使用该货币方案数继承原有f[j]。使用至少一枚该货币相当于在金额j-p[i]的方案基础上增加一枚当前货币方案数为f[j - p[i]]。因此转移方程为f[j] f[j - p[i]]。遍历顺序内层金额从小到大正序遍历适配完全背包“物品可无限选取”的特性允许重复使用当前货币。3. 复杂度分析时间复杂度O ( V × N ) O(V \times N)O(V×N)V为货币种类数N为目标面值。V≤25N≤10000总运算量约25万远低于时间限制。空间复杂度O ( N ) O(N)O(N)使用一维DP数组优化空间仅需存储各金额的方案数。总结核心逻辑将问题转化为完全背包组合方案计数通过一维DP数组正序转移实现无限选取外层枚举货币保证组合不重复计数最终f[N]即为总方案数。关键操作完全背包正序遍历、组合数顺序去重、初始边界f[0]1。效率保障线性递推无冗余计算万级规模下运行极快。代码简要说明数组定义p数组存储所有货币的面值f数组为动态规划数组存储各金额对应的方案数使用long long类型避免数值溢出。初始化设置f[0] 1作为凑0元的基准方案数是所有递推的起点。DP递推外层遍历每种货币逐个加入方案统计体系。内层从当前货币面值开始到目标面值n正序遍历执行方案数累加转移实现完全背包的无限选取效果。结果输出f[n]即为凑出面值n的总方案数使用printf格式化输出结果。输入优化关闭流同步并解绑tie提升输入读取效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll p[400010],f[400010];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll v,n;cinvn;for(ll i1;iv;i)cinp[i];f[0]1;for(ll i1;iv;i)for(ll jp[i];jn;j)f[j]f[j]f[j-p[i]];printf(%lld,f[n]);return0;}