很久以前，魔法世界的人們注重于眼前的享樂，失去了探索宇宙，探索未知世界的興趣，他們經常以急功近利的心態(tài)評價一件事：“這對我有什么用呢？”幸好當時的領導人遠見卓識，他說：“我們歷史上曾經因錯失大航海時代，而導致了長達數百年的衰落。今天，我們不能再錯失太空時代，我們的征途將是星辰大海！”所以現在魔法學院才能夠有足夠的技術實力建造太空梯(用魔法石壘)進入太空以應對天頂星人的威脅。他們有k (1 ≤K ≤ 400)種不同類型的魔法石，每一種魔法石的高度為h（1 ≤ h≤100），數量為c (1 ≤ c ≤10)，由于會受到太空輻射而失去魔力，每一種魔法石不能超過這種魔法石的最大建造高度a (1≤ a≤40000)，試求利用這些魔法石所能修建的太空梯的最高高度。
第一行為一個整數即k。第2行到第k+1行每一行有三個數，代表每種類型魔法石的特征，即高度h，限制高度a和數量c。
一個整數，即修建太空梯的最大高度。
3 7 40 3 5 23 8 2 52 6
48
#include <bits/stdc++.h>using namespace std;struct data { int h,a,c;} d[4005];int f[400005],i,j,k,m,ans;bool cmp(data A,data B) { return A.a<B.a;}int main() { while (~scanf("%d",&k)&&k>0) { memset(f,0,sizeof(f)); ans=0; for (i=1; i<=k; ++i) scanf("%d%d%d",&d[i].h,&d[i].a,&d[i].c); sort(d+1,d+k+1,cmp); for (i=1; i<=k; ++i) { if (d[i].a<d[i].h) continue; while (d[i].c--) { for (j=d[i].a; j>=0; --j) {if (f[j-d[i].h]+d[i].h<=j) f[j]=max(f[j],f[j-d[i].h]+d[i].h);ans=max(ans,f[j]);} } } 不得不說的神級測試用例3 5 10 1 5 20 1 10 10 1
新聞熱點
疑難解答
