首页 > 代码库 > poj 2392 Space Elevator (多重背包)
poj 2392 Space Elevator (多重背包)
Space Elevator
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 8110 | Accepted: 3843 |
题目大意 :一群牛要上天 用一些石块堆塔 给出石块的种类 及其每个种类的数量 和该种石块能出现的最高高度 和每种石块的数量
求怎么摆放才能堆得最高
多重背包模板题。。。。
将所有石块排序 把高度低的放下面
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct Class{ int h,maxh,c; }a[405]; int cmp(Class x,Class y) { return x.maxh<y.maxh; } int main() { int n,ans,i,j,dp[40005],sum[40005]; while(cin>>n) { for( i=0;i<n;i++) cin>>a[i].h>>a[i].maxh>>a[i].c; sort(a,a+n,cmp); memset(dp,0,sizeof(dp)); dp[0]=1; int ans=0; for(i=0;i<n;i++) { memset(sum,0,sizeof(sum)); for(j=a[i].h;j<=a[i].maxh;j++) { if(!dp[j]&&dp[j-a[i].h]&&sum[j-a[i].h]<a[i].c) { dp[j]=1; sum[j]=sum[j-a[i].h]+1;//统计石块放置的个数 if(ans<j) ans=j; } } } cout<<ans<<endl; } return 0; }
poj 2392 Space Elevator (多重背包)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。