题目

Description

　　奶牛们想用K(1<=K<=400)中石块制造一个太空电梯去太空旅行，每种石块有自己的高度h_i(1<=h_i<=100)和数量c_i(1<=c_i<=10),为了避免宇宙射线的干扰，每种石块不能超过最高可以达到的高度a_i(1<=a_i<=40000)。

　　帮助奶牛用石块堆积一个最高的太空电梯。

 

Input

　　第1行：一个整数K

　　第2到K+1行：每行3个用空格隔开的整数h_i,a_i,c_i

Output

　　输出一个高度H，表示最大高度。

 

Sample Input

37 40 35 23 82 52 6

Sample Output

48

 

Data Constraint

 

 

Hint

【样例说明】

　　从上到下依次是6个3号石块、3个1号石块和3个2号石块，注意放4个2号石块在3个1号石块的下面是不行的，因为1号石块最高不能超过40，而现在最上面的1号石块高度达到41，所以不行。

 

分析

显然可设f[i]f[i] 表示是否可以到达高度i

每次枚举高度，看当前的点是否可以到达这个高度就可以了

f[0] = 1

 

代码

1 #include
     
       2 #include
      
        3 using namespace std; 4 struct sb 5 { 6     int val,he,c; 7 }a[1000010]; 8 int f[1000010]; 9 bool cmp(sb a,sb b){
   return a.he
       
        >n;14     for (int i=1;i<=n;i++)15         cin>>a[i].val>>a[i].he>>a[i].c;16     sort(a+1,a+1+n,cmp);17     f[0]=1;18     for (int i=1;i<=n;i++)19         for (int k=a[i].he;k>=0;k--)20           for (int j=1;j<=a[i].c&&k+a[i].val*j<=a[i].he&&f[k]==1;j++)21              f[k+j*a[i].val]=1;22     for (int i=a[n].he;i>=1;i--) 23     {24         if (f[i]) {25             cout<