hdu1248 参考答案

   1 //732185 2008-07-31 12:03:42 Accepted 1248 0MS 12K 556 B G++ whiteTiger 
   2 #include <stdio.h>
   3 
   4 int dp[10001];
   5 
   6 int min(int a, int b, int c){
   7     if(a > b)    a = b;
   8     if(a > c)    a = c;
   9     return a;
  10 }
  11 
  12 void init(){
  13     int i, p1, p2, p3;
  14     int p[3] = {150, 200, 350};
  15     for(i = 0; i < 150; i++)
  16         dp[i] = i;
  17     for(i=150; i< 10001; i++){
  18         p1 = p2 = p3 = 9999;
  19         p1 = dp[i-p[0]];
  20         if(i >= 200)
  21             p2 = dp[i-p[1]];
  22         if(i >= 350)
  23             p3 = dp[i-p[2]];
  24         dp[i] = min(p1, p2, p3);
  25     }
  26 }
  27 
  28 int main(){
  29     init();
  30     int N, m;
  31     scanf("%d", &N);
  32     while(N--){
  33         scanf("%d", &m);
  34         printf("%d\n", dp[m]);
  35     }
  36 
  37     return 0;
  38 }