POJ 2392 Space Elevator（带限制条件的多重背包）

本文主要是介绍POJ 2392 Space Elevator（带限制条件的多重背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://poj.org/problem?id=2392

大意：一群牛用石块堆天梯，不同的石块有不同的高度和最高的堆叠高度，求最终的高度。

分析：觉得是多重背包，但是有了高度的限制。看了别人写的代码半天才缓过来。啊，这样处理。DP路漫漫。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=4e4+10;
struct node{int h,hmax,c;
}stone[410];
int cmp(node a,node b){return a.hmax<b.hmax;
}
int dp[N],sum[N];
int main()
{int n;while(cin>>n){for(int i=0;i<n;i++){scanf("%d%d%d",&stone[i].h,&stone[i].hmax,&stone[i].c);}sort(stone,stone+n,cmp);memset(dp,0,sizeof(dp));dp[0]=1;int ans=0;for(int i=0;i<n;i++){memset(sum,0,sizeof(sum));for(int j=stone[i].h;j<=stone[i].hmax;j++){if(dp[j]==0&&dp[j-stone[i].h]&&sum[j-stone[i].h]<stone[i].c){dp[j]=1;sum[j]=sum[j-stone[i].h]+1;ans=ans>j?ans:j;}}}printf("%d\n",ans);}return 0;
}

这篇关于POJ 2392 Space Elevator（带限制条件的多重背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---