poj——2392——Space Elevator(多重)

发布时间:2014-10-22 18:35:44编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj——2392——Space Elevator(多重)",主要涉及到poj——2392——Space Elevator(多重)方面的内容,对于poj——2392——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 有一群奶牛想到太空去,他们有k中类型的石头,每一类石头高h,石头能达到的高度c,以及它的数量a,在做背包前需要对石块能到达的最大高度(a)进行排序,而且每种砖块都有一个限制条件,就是说以该种砖块结束的最大高度H不能超过某个高度,不同砖块的高度不同。求最高的高度是多少。 3 7 40 3 5 23 8 2 52 6 Sample Output 48 #include <iostream> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; const int M=405; const int MAX=40005; struct node { int h; int a; int c; }Node[M]; int cmp(node a,node b) { return a.a<b.a; } int dp[MAX]; int vis[MAX]; int main() { int t; while(scanf("%d",&t)!=EOF) { for(int i=1;i<=t;i++) scanf("%d%d%d",&Node[i].h,&Node[i].a,&Node[i].c); sort(Node+1,Node+t+1,cmp); memset(vis,0,sizeof(vis)); vis[0]=1; int max=0; for(int i=1;i<=t;i++) { memset(dp,0,sizeof(dp)); for(int j=Node[i].h;j<=Node[i].a;j++) { if(!vis[j]&&vis[j-Node[i].h]&&dp[j-Node[i].h]+1<=Node[i].c) { vis[j]=1; dp[j]=dp[j-Node[i].h]+1; if(j>max) max=j; } } } printf("%d\n",max); } return 0; }