## poj 2392 Space Elevator(多重背包)

2019年04月13日 算法 ⁄ 共 2079字 ⁄ 字号 评论关闭
Space Elevator
 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

```3
7 40 3
5 23 8
2 52 6```

Sample Output

`48`

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

```#include<algorithm>
#include<iostream>
#include<string.h>
#include<sstream>
#include<stdio.h>
#include<math.h>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
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<b.a;
}
void pack(int val,int mou,int lim)//wei==val时的特殊情况
{
for(int i=val;i<=lim;i++)
{
if(f[i])
num[i]=0;
else if(f[i-val])//如果f[i-val]为1有两种可能。1,还没有使用物品i
{                //2,已经使用了物品i。可知1的num为0。2的num洽为使用了的个数
if(i<2*val)//这范围的还没初始化
{
num[i]=1;
f[i]=1;
ans=max(ans,i);
}
else if(num[i-val]<mou)
{
num[i]=num[i-val]+1;
f[i]=1;
ans=max(ans,i);
}
}
}
}
int main()
{
int n,i;

while(~scanf("%d",&n))
{
ans=0;
for(i=0;i<n;i++)
scanf("%d%d%d",&blo[i].h,&blo[i].a,&blo[i].c);
sort(blo,blo+n,cmp);
memset(f,0,sizeof f);
f[0]=1;
for(i=0;i<n;i++)
pack(blo[i].h,blo[i].c,blo[i].a);
printf("%d\n",ans);
}
return 0;
}
```