poj2392-Space Elevator

题目链接

题意：给出n种高度为h方块，每种有c个，求可用方块堆成的塔的最高高度，每种方块在塔中都有其限制高度a,塔中堆叠的方块的高度不可超过a

解法：多重背包

因为按a小则a在下的堆叠方式可得到最高高度，所以根据a对数据进行排序，而后按塔的高度从小往大进行状态转移；

#include
#include
using namespace std;
struct dop{
int a;
int c;
int h;
bool operator < (const dop x) const{
return a>n;
    for(int i=1;i<=40000;i++) dp[i]=-1;
    dp[0]=0;
    for(int i=0;i>p[i].h>>p[i].a>>p[i].c;
    sort(p,p+n);
    for(int i=0;i=0;j--)
    for(int k=1;k<=p[i].c&&k*p[i].h<=j;k++)
    if(dp[j-k*p[i].h]!=-1){
    dp[j]=max(dp[j],dp[j-k*p[i].h]+k*p[i].h);
    ans=max(ans,dp[j]);
    }
    cout<