摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

DP(零錢問題)

/*******************************************************/

#include<stdlib.h>     
#include<stdio.h>     
#include<string.h>  
long long int money[50001],a,b,c,n;  
char x[500000];  
main()     
{     
 long long int cost[10]={1,5,10,20,50,100,200,500,1000,2000};  
 money[0]=1;  
 for(a=0;a<10;a++)  
  for(b=cost[a];b<50001;b++)  
     money[b]=money[b]+money[b-cost[a]];  
 while(gets(x))    
  {  
   if(x[0]==48&&strlen(x)==1) break;  
   if(x[strlen(x)-1]==49&&strlen(x)==1) {printf("0\n");continue;}  
   long long int m=strlen(x);  
   long long temp=0,sum=0;  
   for(a=0;a<m;a++)  
    {  
     if(x[a]<=57&&x[a]>=48)  
      temp=temp*10+x[a]-48;  
     else 
      {  
       sum=sum+temp;  
       temp=0;  
      }   
    }  
    sum=sum+temp;  
    printf("%lld\n",money[sum]-1);  
  }  
 return 0;         
}