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;         
}