题目大意：一群牛想造电梯到太空，电梯都是由一个一个块组成的，每一种块不能超过这个类型的高度，且每一种块都有各自的高度，有固定数量，问最高能造多高。
这题就是1742的翻版，对ai排个序就可以了
（尼玛，我qsort排了n-1个数，wa半天不知所措）
#include <iostream>
#include <functional>
#include <algorithm> using namespace std;
typedef struct _set
{
int h_i;
int max_h;
int count;
}Block;
int fcomp(const void *a, const void *b)
{
return (*(Block *)a).max_h - (*(Block *)b).max_h;
} static int dp[];
static Block B_Set[]; void Search(const int); int main(void)
{
int n;
while (~scanf("%d", &n))
{
if (n == ) continue;
for (int i = ; i <= n; i++)
scanf("%d%d%d", &B_Set[i].h_i, &B_Set[i].max_h, &B_Set[i].count);
qsort(B_Set, n + , sizeof(Block), fcomp);
Search(n);
}
return ;
} void Search(const int n)
{
int i, j;
memset(dp, -, sizeof(dp));
dp[] = ;
for (i = ; i <= n; i++)
{
if (B_Set[i].h_i == ) continue;
for (j = ; j < B_Set[i].h_i && j <= B_Set[i].max_h; j++)//先把前面的几个包确定下来
if (dp[j] != -)
dp[j] = B_Set[i].count;
for (; j <= B_Set[i].max_h; j++)
{
if (dp[j] == -)
{
if (dp[j - B_Set[i].h_i] <= )
continue;
else dp[j] = dp[j - B_Set[i].h_i] - ;
}
else dp[j] = B_Set[i].count;
}
}
for (int i = B_Set[n].max_h; i >= ; i--)
{
if (dp[i] >-)
{
printf("%d\n", i);
break;
}
}
}