题目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个整数代表所有货币的单位面值。输出格式仅一行一个整数代表方案数。输入输出样例 #1输入 #13 10 1 2 5输出 #110说明/提示翻译来自 NOCOW。USACO Training Section 2.3代码1朴素版二维数组#includebits/stdc.husingnamespacestd;constintN2510,M1000010;longlongn,V,v,f[N][M];intmain(){cinnV;f[0][0]1;for(inti1;in;i){cinv;for(intj0;jV;j)for(intk0;k*vj;k)f[i][j]f[i-1][j-k*v];}coutf[n][V];return0;}代码2优化1二维数组#includebits/stdc.husingnamespacestd;constintN2510,M1000010;longlongn,V,v,f[N][M];intmain(){cinnV;f[0][0]1;for(inti1;in;i){cinv;for(intj0;jV;j){f[i][j]f[i-1][j];if(vj)f[i][j]f[i][j-v];}}coutf[n][V];return0;}代码3一维数组#includebits/stdc.husingnamespacestd;constintM1000010;longlongn,V,v,f[M];intmain(){cinnV;f[0]1;for(inti1;in;i){cinv;for(intjv;jV;j)f[j]f[j-v];}coutf[V];return0;}结果