原題：

http://172.16.0.132/senior/#contest/show/2061/1

題目描述：

奶牛們想用K(1<=K<=400)中石塊制造一個(gè)太空電梯去太空旅行，每種石塊有自己的高度h_i(1<=h_i<=100)和數(shù)量c_i(1<=c_i<=10),為了避免宇宙射線的干擾，每種石塊不能超過最高可以達(dá)到的高度a_i(1<=a_i<=40000)。
幫助奶牛用石塊堆積一個(gè)最高的太空電梯。

輸入：

第1行：一個(gè)整數(shù)K
第2到K+1行：每行3個(gè)用空格隔開的整數(shù)h_i,a_i,c_i

輸出：

輸出一個(gè)高度H，表示最大高度。

樣例輸入：

3
7 40 3
5 23 8
2 52 6

樣例輸出：

48

樣例說明：

從上到下依次是6個(gè)3號石塊、3個(gè)1號石塊和3個(gè)2號石塊，注意放4個(gè)2號石塊在3個(gè)1號石塊的下面是不行的，因?yàn)?號石塊最高不能超過40，而現(xiàn)在最上面的1號石塊高度達(dá)到41，所以不行。

分析：

將a[i]排序，做一遍多重背包

實(shí)現(xiàn)：

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