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 }
  39 }
  40 
  41 /*written by zl  876149 2008-11-05 15:59:37 Accepted 1248 0MS 0K 453 B C++ passing */
  42 #include<iostream>
  43 using namespace std;
  44 int main()
  45 {
  46         int casenum;
  47         cin>>casenum;
  48         for(int i=0;i<casenum;i++)
  49         {
  50                 int x,y,z,t,number;
  51                 scanf("%d",&t);
  52                 number=t;
  53                 for(x=0;x<=t/350;x++)
  54                 {
  55                         for(y=0;y<=t/200;y++)
  56                         {
  57                                 for(z=0;z<=t/150;z++)
  58                                 {
  59                                         if((t-350*x-200*y-150*z)<0) break;
  60                                         if((t-350*x-200*y-150*z)<number)
  61                                                 number=t-350*x-200*y-150*z;
  62                                 }
  63                         }
  64                 }
  65                 printf("%d\n",number);
  66         }
  67         return 0;