杭电2191

 1 //大牛的多重背包二进制优化写法
 2 #include<stdio.h>
 3 #include<string.h>
 4 int r[105],v[105],n[105];
 5 int a[1005];
 6 int Room;
 7 
 8 void db(int,int,int);
 9 void lb(int,int);
10 void wb(int,int);
11 
12 int main()
13 {
14     int t;
15     scanf("%d",&t);
16     while(t--)
17     {
18         memset(a,0,sizeof a);
19         int num;
20         scanf("%d%d",&Room,&num);
21         for(int i=0; i<num; ++i)
22         {
23             scanf("%d%d%d",r+i,v+i,n+i);
24             db(r[i],v[i],n[i]);
25         }
26         printf("%d\n",a[Room]);
27     }
28 }
29 
30 void db(int r,int v,int n)
31 {
32     if(n*r >= Room)
33     {
34         wb(r,v);
35         return ;
36     }
37     int k=1;
38     while(k < n)
39     {
40         lb(k*r,k*v);
41         n-=k;
42         k*=2;
43     }
44     lb(n*r,n*v);
45 }
46 
47 void lb(int r,int v)
48 {
49     for(int j=Room; j>=r; --j)
50     {
51         int t = a[j-r]+v;
52         if(a[j] < t)
53             a[j]=t;
54     }
55 }
56 
57 void wb(int r,int v)
58 {
59     for(int j=r; j<=Room; ++j)
60     {
61         int t = a[j-r]+v;
62         if(a[j] < t)
63             a[j]=t;
64     }
65 }