杭电1114

 1 //完全背包，有待改良
 2 #include<stdio.h>
 3 #include<string.h>
 4 typedef struct
 5 {
 6     int val,room;
 7 } cus;
 8 int an[10005];
 9 cus inf[505];
10 int main()
11 {
12     int n;
13     scanf("%d",&n);
14     while(n--)
15     {
16         memset(an,0,sizeof an);
17         memset(inf,0,sizeof inf);
18 
19         int num,rol,ror;
20         scanf("%d%d%d",&rol,&ror,&num);
21 
22         int Room=ror-rol;
23         for(int i=0; i<num; ++i)
24             scanf("%d%d",&inf[i].val ,&inf[i].room);
25 
26         for(int i=0; i<num; ++i)
27         {
28             for(int j=Room; j>0; --j)
29             {
30                 if(j!=Room && !an[j])
31                     continue;
32                 int seet = j-inf[i].room;
33                 if(seet < 0)
34                     break;
35                 int temp = an[j]+inf[i].val;
36                 if((an[seet] && an[seet]>temp) || !an[seet])
37                     an[seet]=temp;
38             }
39         }
40 
41         if(an[0])
42             printf("The minimum amount of money in the piggy-bank is %d.\n",an[0]);
43         else
44             puts("This is impossible.");
45     }
46     return 0;
47 }