题目描述

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

思路

显然可设$f[i]$ 表示是否可以到达高度i
每次枚举高度，看当前的点是否可以到达这个高度就可以了
f[0] = 1

#include <stdio.h>
#include <algorithm>
using namespace std;
struct arr
{
    int h, l, c;
}a[501];
bool f[40001];
int cmp(arr a , arr b)
{
    return a.l < b.l;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d", &a[i].h, &a[i].l, &a[i].c);
    f[0] = 1;
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i++)
        for (int k = a[i].l; k >= 0; k--)
            for (int j = 1; j <= a[i].c && k + a[i].h * j <= a[i].l && f[k] == 1; j++)
                f[k + a[i].h * j] = 1;
    for (int i = a[n].l + 1; i >= 0; i--)
        if (f[i])
        {
            printf("%d\n", i);
            break;
        }
    return 0;
}