USACO 2.3.4 Money Systems 动态归划
Money Systems
The cows have not only created their own government but they have chosen to create their own money system. In their own rebellious way, they are curious about values of coinage. Traditionally, coins come in values like 1, 5, 10, 20 or 25, 50, and 100 units, sometimes with a 2 unit coin thrown in for good measure.
The cows want to know how many different ways it is possible to dispense a certain amount of money using various coin systems. For instance, using a system of {1, 2, 5, 10, ...} it is possible to create 18 units several different ways, including: 18x1, 9x2, 8x2+2x1, 3x5+2+1, and many others.
Write a program to compute how many ways to construct a given amount of money using supplied coinage. It is guaranteed that the total will fit into both a signed long long (C/C++) and Int64 (Free Pascal).
PROGRAM NAME: money
INPUT FORMAT
The number of coins in the system is V (1 <= V <= 25).
The amount money to construct is N (1 <= N <= 10,000).
Line 1: Two integers, V and N
Lines 2..: V integers that represent the available coins (no particular number of integers per line)
SAMPLE INPUT (file money.in)
3 10
1 2 5
OUTPUT FORMAT
A single line containing the total number of ways to construct N money units using V coins.
SAMPLE OUTPUT (file money.out)
10
/*---------------------------------------------------------------------------------------*/
又回到了动态规划，这道题就是很经典的硬币找零问题了。我用的是二维数组的方式（我记得还有一种空间性能更好的一维数组方式）。
基本思想就是，设要找i元钱，我们先只使用前j种硬币来完成。现在我们要记录的是，在确保一定使用第j种硬币的情况下，有多少种找法。那么如何确保第j种硬币一定会被使用呢？就是在i元钱上面减去第j种硬币的面值，然后去看看使用前j种硬币的情况下，i-j元钱有多少种找法，全部加起来。特别地，如果i-j是0的话，就要加上1，代表直接找了这个硬币。
因此我们使用一个二维数组method[i][j]来记录，在使用前j种硬币且保证使用第j种硬币的情况下，找出i元钱有多少种找法。
还要说一句的是，不知道为什么，一开始我的程序在我自己的电脑上的运行结果与在USACO上的运行结果不同，怎么也找不出问题。后来我把二维数组的规模从10000扩大到10003，就好了。
程序：
[cpp]
/*
ID:zhaorui3
PROG:money
LANG:C++
*/
# include <fstream>
using namespace std;
int kinds[26] = {0};
long long methods[10010][26] = {{0}};
int main()
{
ifstream fin("money.in");
ofstream fout("money.out");
int v , n;
fin >> v >> n;
for (int i = 0; i < v; ++i)
fin >> kinds[i];
for(int i = 1 ; i <= n ; i++ )
{
for(int j = 0 ; j < v ; j++ )
{
if(i < kinds[j])
continue;
for (int k = 0; k <= j; ++k)
{ www.zzzyk.com
if(i-kinds[j] != 0)
methods[i][j] += methods[i-kinds[j]][k];
}
if(i-kinds[j] == 0)
methods[i][j]++;
}
}
long long out = 0;
for (int i = 0; i < v; ++i)
out += methods[n][i];
fout << out << endl;
fin.close();
fout.close();
return 0;
}
补充：软件开发 , C++ ,
