UVa 147 Dollars

之前解的，忘了貼上來。
這是個典型的Dynamic Programming問題。
可是我忘記遞迴式是什麼了..囧 改天補上

	/**
	* UVa 147 Dollars
	* Author: chchwy
	* Last Modified: 2009.12.05
	*/
	#include<cstdio>
	enum {MAX = 30000 + 1, NUM_COIN = 11};
	long long int count[MAX]; //unit is cent
	int main()
	{
	int coin[NUM_COIN] = {5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};
	//build dp table
	count[0] = 1;
	for (int i = 0; i < NUM_COIN; ++i)
	for (int j = coin[i]; j < MAX; j += 5) //bug: use int j=5
	count[j] += count[ j - coin[i] ];
	int dollar, cent;
	while (scanf("%d.%d", &dollar, &cent) == 2)
	{
	if (dollar == 0 && cent == 0) break;
	printf("%3d.%02d%17lld\n", dollar, cent, count[dollar * 100 + cent]);
	}
	return 0;
	}

view raw 147.cpp hosted with ❤ by GitHub