本文共 1358 字，大约阅读时间需要 4 分钟。
题目：
题目大意：
有n种砖头，每种砖头的高为h，数量为c， 且它放的最高位置不能超过a。 问这些砖最高能够叠多高？
思路：
先把所有种类砖头按照a从大到小排序，然后直接套多重背包即可。
代码：
#include #include #include #include #include #include #include #include #include #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://yvzni.baihongyu.com/