算法：poj 2392 Space Elevator（dp 排序+多重背包）

算法：poj 2392 Space Elevator（dp 排序+多重背包）2014-01-10 csdn shuangde800题目大意：

有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
", ans）;return 0;}