HDOJ1114解题报告

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <vector>
 6 #include <ctime>
 7 #include <map>
 8 #include <stack>
 9 #include <queue>
10 #include <cstring>
11 #include <algorithm>
12 using namespace std;
13 
14 #define sacnf scanf
15 #define scnaf scanf
16 #define scanfi(x) scanf("%d",&x)
17 #define scanfd(x) scanf("%lf",&x)
18 #define scanfl(x) scanf("%lld",&x)
19 #define scanfc(x) scanf("%c",&x)
20 #define scanfs(x) scanf("%s",x)
21 #define maxn  510
22 #define maxm 10010
23 #define inf 1061109567
24 #define Eps 0.00001
25 const double PI=acos(-1.0);
26 #define mod 1000000007
27 #define MAXNUM 10000
28 void Swap(int &a,int &b) {int t=a;a=b;b=t;}
29 int Abs(int x) {return (x<0)?-x:x;}
30 typedef long long ll;
31 typedef unsigned int uint;
32 
33 int dp[maxm];
34 
35 int main()
36 {
37     //freopen("data.in","r",stdin);
38     //freopen("data.out","w",stdout);
39     //clock_t st=clock();
40     int T;scanf("%d",&T);
41     while(T--)
42     {
43         int E,F,p,w,n;scanf("%d%d",&E,&F);F-=E;
44         memset(dp,0x3f,sizeof(dp));scanf("%d",&n);
45         dp[0]=0;
46         for(int i=1;i<=n;i++)
47         {
48             scnaf("%d%d",&p,&w);
49             for(int j=w;j<=F;j++)
50                 dp[j]=min(dp[j],dp[j-w]+p);
51         }
52         if(dp[F]==inf) printf("This is impossible.\n");
53         else printf("The minimum amount of money in the piggy-bank is %d.\n",dp[F]);
54     }
55     //clock_t ed=clock();
56     //printf("\n\nTime Used : %.5lf Ms.\n",(double)(ed-st)/CLOCKS_PER_SEC);
57     return 0;
58 }