算法：poj 2392 Space Elevator(dp 排序+多重背包)

题目大意：

有n种砖头，每种砖头的高为h，数量为c， 且它放的最高位置不能超过a。 问这些砖 最高能够叠多高？

思路：

先把所有种类砖头按照a从大到小排序，然后直接套多重背包即可 。

代码：

#include<iostream>
#include<queue>
#include<stack>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<string>
#define MP make_pair
#define SQ(x) ((x)*(x))
#define MAX(x, y) ((x)>(y))?(x):(y)
typedef int int64;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
using namespace std;  

const int MAXN = 33;  

int n, m;  

struct Node{
    int h, a, c;
    bool operator<(const Node& rhs)const {
        return a < rhs.a;
    }
}arr[410];  

inline void ZeroOnePack(int* f, int V, int c, int w){
    for(int i=V; i>=c; --i)
        f[i] = max(f[i], f[i-c]+w);
}
inline void CompletePack(int* f, int V, int c, int w){
    for(int i=c; i<=V; ++i)
        f[i] = max(f[i], f[i-c]+w);
}
inline void MultiplePack(int* f, int V, int c, int w, int m){
    if(c*m >= V){
        CompletePack(f, V, c, w);
        return ;
    }
    int k = 1;
    while(k < m){
        ZeroOnePack(f, V, k*c, k*w);
        m -= k;
        k <<= 1;
    }
    ZeroOnePack(f, V, m*c, m*w);
}  

int f[100010];  

int main(){  

    scanf("%d", &n);
    int maxx = 0;
    for(int i=1; i<=n; ++i){
        scanf("%d%d%d", &arr[i].h,&arr[i].a,&arr[i].c);
        maxx = max(maxx, arr[i].a);
    }  

    sort(arr+1, arr+1+n);  

    for(int i=0; i<=maxx; ++i)
        f[i] = 0;  

    for(int i=1; i<=n; ++i)
        MultiplePack(f, arr[i].a, arr[i].h, arr[i].h, arr[i].c);  

    int ans = 0;
    for(int i=0; i<=maxx; ++i)
        ans = max(ans, f[i]);
    printf("%d\n", ans);
    return 0;
}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， include
， 背包问题
， const
， define
， c 回溯 背包
， w y f
， elevation
， 多重
背包
space elevator、背包dp、dp背包问题、lu2392撸尔山永久地址、2392 39 4，以便于您获取更多的相关知识。