poj2392 Space Elevator( dp ,背包)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 //#pragma comment (linker,"/STACK:1024000000,1024000000")
 6 #define MAXN 500
 7 #define INF 0x7ffffff
 8 int n;
 9 struct P
10 {
11     int h,c,a;
12 
13     bool operator < (const P& x) const
14     {
15         return a<x.a;
16     }
17 };
18 
19 int dp[MAXN][40000+10];
20 
21 P w[MAXN];
22 int hmax = 0;
23 void init()
24 {
25     cin>>n;
26     for(int i=0;i<n;i++)
27     {
28         cin>>w[i].h>>w[i].a>>w[i].c;
29         hmax  = max(hmax , w[i].a);
30     }
31     sort(w,w+n);
32     for(int i=0;i<=n;i++)
33     {
34         for(int ta=0;ta<=hmax;ta++)
35             dp[i][ta] = -1;
36     }
37     dp[0][0] = 0;
38 }
39 
40 int main()
41 {
42     init();
43 
44     for(int i=1;i<=n;i++)
45     {
46         for(int ta = 0 ; ta<=w[i-1].a;ta++)
47         {
48             if( dp[i-1][ta] >=0 )
49             {
50                 dp[i][ta]  = w[i-1].c;
51             }
52             else if( ta<w[i-1].h|| dp[i][ ta - w[i-1].h]<=0)
53             {
54                 dp[i][ta] = -1;
55             }
56             else
57             {
58                 dp[i][ta] = dp[i][ ta- w[i-1].h] - 1;
59             }
60         }
61     }
62 
63     for(int i=hmax;i>=0;i--)
64     {
65         if(dp[n][i]>=0)
66         {
67             cout<<i<<endl;
68             break;
69         }
70     }
71 
72     return 0;
73 }