原題鏈接 Space Elevator Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 11392 Accepted: 5433 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
USACO 2005 March Gold
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int maxn = 40000 + 10;typedef struct blocks{ int h,a,c;}blocks;blocks a[410];int dp[maxn];bool cmp(blocks x,blocks y){ return x.a < y.a;}int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].h,&a[i].a,&a[i].c); sort(a+1,a+1+n,cmp);//對(duì)最大高度進(jìn)行排序再按照多重背包的方法處理就好了 memset(dp,-1,sizeof(dp)); for(int i=1;i<=n;i++){ dp[0] = a[i].c; for(int j=1;j<=a[i].a;j++){ if(dp[j] >= 0) dp[j] = a[i].c; else if(j < a[i].h || dp[j-a[i].h] <= 0) dp[j] = -1; else dp[j] = dp[j-a[i].h] - 1; } } int loc=0;//注意這里一定要初始化為0，因?yàn)橛锌赡芙o出的石頭一個(gè)都不能用來(lái)搭電梯 for(int i = a[n].a;i>0;i--){ if(dp[i] >= 0){ loc = i; break; } } cout << loc << endl; return 0;}//下面是標(biāo)準(zhǔn)的滾動(dòng)數(shù)組的形式，實(shí)際上本題可以更簡(jiǎn)化為1維dp如上// #include <cstdio>// #include <cstring>// #include <iostream>// #include <algorithm>// using namespace std;// const int maxn = 40000 + 10;// typedef struct blocks// {// int h,a,c;// }blocks;// blocks a[410];// int dp[2][maxn];// bool cmp(blocks x,blocks y){// return x.a < y.a;// }// int main(){// int n;// scanf("%d",&n);// for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].h,&a[i].a,&a[i].c);// sort(a+1,a+1+n,cmp);//對(duì)最大高度進(jìn)行排序再按照多重背包的方法處理就好了// memset(dp,-1,sizeof(dp));// for(int i=1;i<=n;i++){// dp[i&1][0] = a[i].c;// for(int j=1;j<=a[i].a;j++){// if(dp[(i-1)&1][j] >= 0) dp[i&1][j] = a[i].c;// else if(j < a[i].h || dp[i&1][j-a[i].h] <= 0) dp[i&1][j] = -1;// else dp[i&1][j] = dp[i&1][j-a[i].h] - 1;// }// }// int loc=0;//注意這里一定要初始化為0，因?yàn)橛锌赡芙o出的石頭一個(gè)都不能用來(lái)搭電梯// for(int i = maxn - 1;i>0;i--){// if(dp[n&1][i] >= 0){// loc = i;// break;// }// }// cout << loc << endl;// return 0;// }新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
