POJ 2392 Space Elevator
题意：解题过程：AC代码：
POJ 2392 Space Elevator
题目传送门
题意：
你需要建一个高塔，材料总共有K种，每种材料有三个属性：高度，数量，限度。限度是指该种材料只能在低于该限度的高度下被使用。问你最高能够把这个高塔建到多高。
解题过程：
这题中材料有高度和数量，比较容易的想到这题是一道多重背包的题目，但是这题有一个限度的限制，使得一些材料在一定高度以上就不能使用，所以我们可以对材料按限度排序，然后就是朴素的多重背包加上一些非法方案的去除就行了。
AC代码：
#pragma GCC optimize (3)
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <vector>
#include <cstdlib>
#include <cstring>
using namespace std;
const int maxn=
500;
int n;
struct mat {
int h,a,c;
}m[maxn];
bool f[
50005];
bool cmp(mat x,mat y) {
return x.a<y.a;
}
int main() {
scanf(
"%d",&n);
int ttop=-
1;
for(
int i=
1;i<=n;i++) {
scanf(
"%d%d%d",&m[i].h,&m[i].a,&m[i].c);
ttop=max(ttop,m[i].a);
}
sort(m+
1,m+
1+n,cmp);
f[
0]=
1;
for(
int i=
1;i<=n;i++) {
int top=m[i].a;
for(
int j=top;j>=
0;j--) {
if(!f[j])
continue;
for(
int k=
1;k<=m[i].c;k++) {
int t=j+k*m[i].h;
if(t<=m[i].a)f[t]=
1;
}
}
}
for(
int i=ttop;i>=
0;i--) {
if(f[i]) {
printf(
"%d\n",i);
return 0;
}
}
}
本人蒟蒻OIer一枚，欢迎加QQ：840776708一起学习蛤。
转载于:https://www.cnblogs.com/Apocrypha/p/9433664.html
相关资源：JAVA上百实例源码以及开源项目
