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 }
知识兔View Code