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.2cto.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; }
