UVa 357 Let Me Count The Ways

跟147、674同樣的題目，順便就吃下來啦
我發現IE會讓我的程式碼排版亂掉，真讓人困擾@_@

	/**
	* UVa 357 The Me Count The Ways
	* Author: chchwy
	* Last Modified: 2010.03.01
	*/
	#include<iostream>
	enum {MAX_MONEY = 30000, COIN_TYPES = 5};
	int main()
	{
	int coin[] = {1, 5, 10, 25, 50};
	long long int count[MAX_MONEY + 1];
	memset(count, 0, sizeof(count));
	/* DP to build count table */
	count[0] = 1;
	for (int i = 0; i < COIN_TYPES; ++i)
	for (int j = coin[i]; j <= MAX_MONEY; ++j)
	count[j] += count[j - coin[i]];
	/* just lookup table */
	int money;
	while ( scanf("%lld", &money) == 1 )
	{
	if ( count[money] == 1 )
	printf("There is only 1 way to produce %d cents change.\n", money);
	else
	printf("There are %lld ways to produce %d cents change.\n", count[money], money);
	}
	return 0;
	}

view raw 357.cpp hosted with ❤ by GitHub