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

79愛的鼓勵 1訂閱站台

這題是DP的1種 零錢問題!

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

#include<stdlib.h>     
#include<stdio.h>     
main()     
{     
 long long int cost[400]={0},m=0;  
 long long int money[751]={0},a,b;
 int n;  
 money[0]=1;
 for(a=1;a<750;a=a+2,m++)
  cost[m]=a;
 for(a=0;a<m;a++)  
  for(b=cost[a];b<=750;b++)  
   money[b]=money[b]+money[b-cost[a]];
 while(scanf("%d",&n)==1)
  while(n--)
   {
    scanf("%lld",&m);
    printf("%lld\n",money[m]);
   }
 return 0;         
}