原题:
http://172.16.0.132/senior/#contest/show/2061/1
题目描述:
奶牛们想用K(1<=K<=400)中石块制造一个太空电梯去太空旅行,每种石块有自己的高度h_i(1<=h_i<=100)和数量c_i(1<=c_i<=10),为了避免宇宙射线的干扰,每种石块不能超过最高可以达到的高度a_i(1<=a_i<=40000)。
帮助奶牛用石块堆积一个最高的太空电梯。
输入:
第1行:一个整数K
第2到K+1行:每行3个用空格隔开的整数h_i,a_i,c_i
输出:
输出一个高度H,表示最大高度。
样例输入:
3
7 40 3
5 23 8
2 52 6
样例输出:
48
样例说明:
从上到下依次是6个3号石块、3个1号石块和3个2号石块,注意放4个2号石块在3个1号石块的下面是不行的,因为1号石块最高不能超过40,而现在最上面的1号石块高度达到41,所以不行。
分析:
将a[i]排序,做一遍多重背包
实现:
#include<cstdio>
#include<algorithm>
using namespace std;
typedef struct
{
int h;
int a;
int c;
}id;
int f[40001];
bool cmp(const id &s1, const id &s2){return s1.a < s2.a;}
int main()
{
int n;
id s[401];
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d%d%d", &s[i].h, &s[i].a, &s[i].c);
sort(s,s+n,cmp);
f[0]=1;
for(int i=0;i<n;i++)
for(int j=s[i].a;j>=0;j--)
for(int k=1;k<=s[i].c;k++)
if(j-s[i].h*k>=0 && f[j-s[i].h*k]!=0) f[j] = 1;
for(int i=40001;i>=0;i--)
if (f[i])
{
printf("%d\n", i);
break;
}
}