1. /**********************************************************************************/  
2. /*  Problem: d119 "有獎徵答：換零錢" from B88000005                       */  
3. /*  Language: C++                                                                 */  
4. /*  Result: TLE (1 secs)  on ZeroJudge                                            */  
5. /*  Author: jacob at 2010-02-24 19:43:34                                          */  
6. /**********************************************************************************/  
7.   
8. # include <iostream.h>    
9.     
10. main()    
11. {    
12.   int money[11]={0,1,5,10,20,50,100,200,500,1000,2000};    
13.   long long int tab[11][52000];    
14.   int sum,i,j,k,l;    
15.   char s[9999];    
16.   while(cin.getline(s,9999))    
17.   {    
18.     l=strlen(s);    
19.     s[l++]=' ';s[l]='\0';    
20.     sum=0;k=0;    
21.         
22.     for(i=0;i<l;i++)    
23.       {    
24.         if (s[i]==' ')    
25.           {    
26.             sum+=k;    
27.             k=0;    
28.           }    
29.         else    
30.           k=k*10+s[i]-48;          
31.       }    
32.           
33.     for(i=1;i<=sum;i++)tab[0][i]=0;    
34.     tab[0][0]=1;    
35.     for(i=1;!((money[i]>sum) ||(i>10));i++)    
36.       {    
37.         for(j=0;j<=money[i];j++) tab[i][j]=tab[i-1][j];   
38.            
39.         for(j=0;j<=sum-money[i]+1;j++) tab[i][j+money[i]]=tab[i][j]+tab[i-1][j+money[i]];    
40.       }    
41.     //brow();    
42.     i--;    
43.     cout<<(tab[i][sum]-1)<<endl;    
44.   }    
45.       
46.  }   
    

code感覺很奇怪 . . . (跟零錢問題傳統DP差很多. . .)

先不論這樣結果對不對

很大的bug就是

每讀進去 你就1~n再做一次

請在while迴圈外預先算出1~50000的值

速度會快很多ˇ

非常感谢，已经通过。没有想到这个bug这么致命……，

原来的写法，一共3800+行的测资跑下来的确很浪费。

因为算法是自己摸索出来的，没有参照过经典案例，可能看起来比较奇怪。^v^