2017.07.15【NOIP提高组】模拟赛B组 太空电梯 题解

原题：

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;
        }
}