POJ.2392 Space Elevator

1.Problem
http://poj.org/problem?id=2392

2.Idea
dp[j]: Can reach to heights of j.
First sort all blocks by possible heights limit - a_i. Then update the dp table for each block type h_i.

3.Source

 struct Block {  
      int a, h, c;  
      bool operator < (const Block &A)const {  
           return A.a > a;  
      }  
 } Blocks[402];  
 int k;  
 int dp[40004];  
 int main()  
 {  
      cin >> k;  
      for (int i = 0; i < k; i++) {  
           int A, H, C;  
           cin >> H >> A >> C;  
           Blocks[i].h = H;  
           Blocks[i].a = A;  
           Blocks[i].c = C;  
      }  
      sort(Blocks, Blocks + k);  
      dp[0] = true;  
      for (int i = 0; i < k; i++) {  
           for (int j = 40000; j >= 0; j--) {  
                if (dp[j]) {  
                     for (int g = 1; g <= Blocks[i].c; g++) {  
                          if (j + Blocks[i].h * g <= Blocks[i].a) dp[j + Blocks[i].h * g] = true;  
                          else break;  
                     }  
                }  
           }  
      }  
      int ans;  
      for (int i = 40000; i >= 0; i--) {  
           if (dp[i]) {  
                ans = i;  
                break;  
           }  
      }  
      cout << ans << endl;  
      return 0;  
 }