首页 > 其他 > 详细

【类背包】P1156 垃圾陷阱

时间:2019-10-09 14:07:44      阅读:155      评论:0      收藏:0      [点我收藏+]
技术分享图片
 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

 

【类背包】P1156 垃圾陷阱

原文:https://www.cnblogs.com/thjkhdf12/p/11641141.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!