2009-03-07 21:54:46來源不明
ACM 357 Q357: Let Me Count The Ways
DP找零錢問題
/************************************************************/
#include<stdlib.h>
#include<stdio.h>
main()
{
long long int cost[5]={1,5,10,25,50};
long long int money[30001]={0},a,b,n;
money[0]=1;
for(a=0;a<5;a++)
for(b=cost[a];b<30001;b++)
money[b]=money[b]+money[b-cost[a]];
while(scanf("%lld",&n)==1)
if(money[n]!=1)
printf("There are %lld ways to produce %lld cents change.\n",money[n],n);
else
printf("There is only 1 way to produce %lld cents change.\n",n);
return 0;
}