【类背包】P1156 垃圾陷阱

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int dp[101][1001];
 6 
 7 struct rub
 8 {
 9     int t, g, h;
10 }c[101];
11 
12 bool cmp(rub a, rub b)
13 {
14     return a.t < b.t;
15 }
16 
17 int main()
18 {
19     int d, g;
20     cin >> d >> g;
21     for (int i = 1; i <= g; i++)
22     {
23         cin >> c[i].t >> c[i].g >> c[i].h;
24     }
25     sort(c + 1, c + g + 1, cmp);
26     dp[0][0] = 10;
27     for (int i = 1; i <= g; i++)
28     {
29         for (int j = 0; j <= d; j++)
30         {
31             if (dp[i - 1][j] >= c[i].t)
32                 dp[i][j] = max(dp[i][j], dp[i-1][j]+c[i].g);
33             if (j >= c[i].h && dp[i - 1][j - c[i].h]>=c[i].t)
34                 dp[i][j] = max(dp[i][j], dp[i - 1][j - c[i].h]);
35         }
36     }
37     int maxh = 0;
38     int maxt = 0;
39     int i;
40     for (i = 1; i <= g; i++)
41     {
42         for (int j = 0; j <= d; j++)
43         {
44             if (dp[i][j] - c[i].t >= 0)
45                 maxh = max(maxh, j);
46             maxt = max(maxt, dp[i][j]);
47         }
48         if (maxh >= d)
49             break;
50     }
51     if (maxh >= d)
52         cout << c[i].t << endl;
53     else
54         cout << maxt << endl;
55 }