2017.07..15【NOIP向上組】模擬試合B組宇宙エレベータークイズ

原題:
http://172.16.0.132/senior/#contest/show/2061/1
テーマの説明:
乳牛たちはK（1<=K==400）の中の石ころを使って宇宙エレベーターを作って宇宙旅行に行きたいです。石ごとに高さがあります。i（1<=hui<=100）と数量c_i（1<=cui<=10）は、宇宙放射線の干渉を避けるために、各石が最高の高さa_を超えてはいけない。i（1<=auui<=40000）乳牛を手伝って石で最高の宇宙エレベーターを積み上げます。
入力:
1行目：1つの整数Kは2行目からK＋1行目：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
#include
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=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
", i);
            break;
        }
}