[POJ] 2392 Space Elevator.cpp

#include <cstdio>
#include <algorithm>
using namespace std;
int dp[40005] = {0};
struct Block{
    int h;
    int a;
    int c;
}b[401];
bool cmp(const Block &a, const Block &b)
{
    return a.a < b.a;
}
int main()
{
    int K;
    while (scanf("%d", &K) != EOF) {
        // Input
        for (int k = 0; k < K; ++k)
            scanf("%d %d %d", &b[k].h, &b[k].a, &b[k].c);
        
        sort(b, b+K, cmp);

        // Knapsack
        fill(dp, dp+40005, 0);
        for (int k = 0; k < K; ++k)
            for (int i = 0; i < b[k].c; ++i)
                for (int j = b[k].a; j-b[k].h >= 0; --j)
                    dp[j] = max(dp[j], dp[j-b[k].h] + b[k].h);
        // Ouput
        int ans = 0;
        for (int i = 0; i <= b[K-1].a; ++i)
            ans = max(ans, dp[i]);
        printf("%d\n", ans);
    }
}