147-Dollars

<br /> /* <br /> "Dollars"<br /> Level:4.5<br /> Date:2006/9/30<br /> 技巧:Dynamic programming <br /> 參357 <br /> */<br /> #include <stdio.h><br /> #define N 11<br /> #define M 6010<br /> main(){<br /> int coin[N]={1,2,4,10,20,40,100,200,400,1000,2000};<br /> long long table[M]={0};<br /> float cent=0.0f;<br /> int i=0,j=0;<br /> <br /> table[0]=1; <br /> for(i=0;i < N;i++){ for(j=coin[i];j < M;j++) table[j]+=table[j-coin[i]]; } while(scanf("%f",¢)){ if(cent == 0.00) break; /* 浮點數做casting要很小心,最好的做法是,先轉成字串,然後用實數部分做除法, 商數再加回浮點數 */ i = (int)((cent*100+0.5)/5); /* 上傳ACM,%17I64d 要改成%17lld */ printf("%6.2f%17I64d\n",cent,table[i]); } }