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; }