poj 2392 Space Elevator(多重背包) - c++编程基础

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 7618		Accepted: 3591

Description

The cows are going to space! They plan to achieve orbit by building a sort of space elevator: a giant tower of blocks. They have K (1 <= K <= 400) different types of blocks with which to build the tower. Each block of type i has height h_i (1 <= h_i <= 100) and is available in quantity c_i (1 <= c_i <= 10). Due to possible damage caused by cosmic rays, no part of a block of type i can exceed a maximum altitude a_i (1 <= a_i <= 40000).

Help the cows build the tallest space elevator possible by stacking blocks on top of each other according to the rules.

Input

* Line 1: A single integer, K

* Lines 2..K+1: Each line contains three space-separated integers: h_i, a_i, and c_i. Line i+1 describes block type i.

Output

* Line 1: A single integer H, the maximum height of a tower that can be built

Sample Input

Sample Output

Hint

OUTPUT DETAILS:

From the bottom: 3 blocks of type 2, below 3 of type 1, below 6 of type 3. Stacking 4 blocks of type 2 and 3 of type 1 is not legal, since the top of the last type 1 block would exceed height 40.

Source

USACO 2005 March Gold

题意：

给你n种砖。告诉你每种砖的高度，数目。和最多承受高度(也就是最大能处的海拔)。问你用这些砖能建多高。

思路：

先按最大承受海拔排序然后多重背包。f[i]表示。1高度i能达到。0为不能。

由于最大承受海拔的原因更新范围有限必须排序。不排序就不是最优的。

详细见代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
             //#pragma comment(linker,"/STACK:1024000000,1024000000") using namespace std; const int INF=0x3f3f3f3f; const double eps=1e-8; const double PI=acos(-1.0); const int maxn=40010; typedef __int64 ll; int num[maxn],f[maxn],ans; struct node { int h,a,c; } blo[450]; bool cmp(node a,node b) { return a.a