题目:点击打开链接
题目大意:
有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;
}
分享到:
相关推荐
这是我的第三篇结题报告,欢迎大家指正!!!!!!!!!!!!!
北大POJ1014-Dividing【DFS】【多重背包+二进制优化】 解题报告+AC代码
晒代码之二——多重背包(POJ1276)
北大POJ1696-Space Ant 解题报告+AC代码
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ1159-Palindrome 解题报告+AC代码
西北工业大学POJ试题C++答案代码+课程设计
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ2002-Squares 解题报告+AC代码
北大POJ初级-所有题目AC代码+解题报告
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
POJ1837-Balance 解题报告+AC代码
北大POJ2503-Babelfish 解题报告+AC代码
北大POJ1201-Intervals 解题报告+AC代码
北大POJ1011-Sticks 解题报告+AC代码
北大POJ1039-Pipe 解题报告+AC代码