|
Space Elevator
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 |
题意：
给你n种砖。告诉你每种砖的高度，数目。和最多承受高度(也就是最大能处的海拔)。问你用这些砖能建多高。
思路：
先按最大承受海拔排序然后多重背包。f[i]表示。1高度i能达到。0为不能。
由于最大承受海拔的原因更新范围有限必须排序。不排序就不是最优的。
详细见代码：
#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>
//#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<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;
}