d119: 有獎徵答：換零錢

解題心得

題目寫得很亂，就沒有仔細看了。

基本上就是零錢問題，記得字串切割跟最後答案要-1就好。

程式碼

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

int prices[10] = { 1,5,10,20,50,100,200,500,1000,2000 };
long long int ans[50001] = { 1 };

int main()
{
	for (int i = 0; i < 10; i++)
	{
		for (int j = prices[i]; j < 50001; j++)
			ans[j] += ans[j - prices[i]];
	}
	string s;
	while (getline(cin, s))
	{
		int n = 0, temp;
		stringstream ss(s);
		while (ss >> temp)
			n += temp;
		if (n == 0) break;
		cout << ans[n] - 1 << endl;
	}
	return 0;
}