题目大意：有一头奶牛要上太空，他有很多种石头，每种石头的高度是hi，但是不能放到ai之上的高度，并且这种石头有ci个

将这些石头叠加起来，问能够达到的最高高度。

题意转载自：http://blog.csdn.net/wangjian8006/article/details/7607745

思路：

按a[i]排个序，多重背包。

// by SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int k,f[40150];

struct node{int h,a,c;}s[401];

bool cmp(node a,node b){return a.a<b.a;}

int main(){

    scanf("%d",&k);

    for(int i=1;i<=k;i++)

        scanf("%d%d%d",&s[i].h,&s[i].a,&s[i].c);

    memset(f,0x3f,sizeof(f)),f[0]=0;

    sort(s+1,s+1+k,cmp);

    for(int i=1;i<=k;i++){

        for(int j=0;j<=s[i].a-s[i].h;j++)

            if(f[j]!=0x3f3f3f3f&&f[j]<s[i].c)

                f[j+s[i].h]=min(f[j]+1,f[j+s[i].h]);

        for(int j=0;j<=s[i].a;j++)if(f[j]!=0x3f3f3f3f)f[j]=0;

    }

    for(int i=40100;i>=0;i--)

        if(f[i]!=0x3f3f3f3f){printf("%d\n",i);break;}

}