hdu--2191--终于可以说出dp水题这句话了-.-

这题是上一题的 recommend 过来的很水..

虽然是多重背包但是因为数据太小了完全可以不用二进制拆分去做

我两者都去写了下 ...都是0ms..

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int size = 110;
 7 int weight[size*20];
 8 int val[size*20];
 9 int dp[size];
10 
11 int main()
12 {
13     cin.sync_with_stdio(false);
14     int t , n , m , cnt , a , b , c;
15     cin >> t;
16     while(t--)
17     {
18         cin >> n >> m;
19         cnt = 0;
20         memset( dp , 0 , sizeof(dp) );
21         for( int i = 1 ; i<=m ; i++ )
22         {
23             cin >> a >> b >> c;
24             for( int j = 1 ; j<=c ; j<<=1 )
25             {
26                 val[cnt] = j * a;
27                 weight[cnt++] = j*b;
28                 c -= j;
29             }
30             if(c)
31             {
32                 val[cnt] = c*a;
33                 weight[cnt++] = c*b;
34             }
35         }
36         for( int i = 0 ; i<cnt ; i++ )
37         {
38             for( int j = n ; j>=val[i] ; j-- )
39             {
40                 dp[j] = max( dp[j] , dp[ j-val[i] ] + weight[i] );
41             }
42         }
43         cout << dp[n] << endl;
44     }
45     return 0;
46 }

View Code

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int size = 110;
 7 int weight[size*20];
 8 int val[size*20];
 9 int dp[size];
10 
11 int main()
12 {
13     cin.sync_with_stdio(false);
14     int t , n , m , cnt , a , b , c;
15     cin >> t;
16     while(t--)
17     {
18         cin >> n >> m;
19         cnt = 0;
20         memset( dp , 0 , sizeof(dp) );
21         for( int i = 1 ; i<=m ; i++ )
22         {
23             cin >> a >> b >> c;
24             while(c--)
25             {
26                 weight[cnt] = b;
27                 val[cnt++] = a;
28             }
29         }
30         for( int i = 0 ; i<cnt ; i++ )
31         {
32             for( int j = n ; j>=val[i] ; j-- )
33             {
34                 dp[j] = max( dp[j] , dp[ j-val[i] ] + weight[i] );
35             }
36         }
37         cout << dp[n] << endl;
38     }
39     return 0;
40 }

View Code

今天下午网络赛我要认真了 -.-

just follow your heart