「POJ2392」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
|
1 2 3 4 |
3 7 40 3 5 23 8 2 52 6 |
Sample Output
|
1 |
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.
题解
首先按照a升序排序
a小的必然要先处理、
然后该怎么做怎么做。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; int n,ans;bool f[40001]; int use[40001]; struct data{int h,a,c;}a[401]; bool cmp(data a,data b){return a.a<b.a;} int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].h,&a[i].a,&a[i].c); f[0]=1; sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++) { memset(use,0,sizeof(use)); for(int j=a[i].h;j<=a[i].a;j++) { if(!f[j]&&f[j-a[i].h]&&use[j-a[i].h]+1<=a[i].c) { f[j]=1; use[j]=use[j-a[i].h]+1; ans=max(ans,j); } } } printf("%d",ans); return 0; } |
Subscribe
计数器 9774156
OI 课件=>
OI 课件=>