HDU 2191 문천 대지진

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <numeric>

using namespace std;

const int MAX = 102;

struct _ {
    const int none = -1;

    int money, dp[MAX];

    void clear(int n) {
        fill(dp, dp + (sizeof dp) / (sizeof dp[0]), none);
        dp[0] = 0;
        money = n;
    }

    void zero_one(int price, int value) {
        for (int c = money; price <= c; --c) {
            if (dp[c - price] != none) {
                dp[c] = max(dp[c], dp[c - price] + value);
            }
        }
    }

    void complete(int price, int value) {
        for (int c = price; c <= money; ++c) {
            if (dp[c - price] != none) {
                dp[c] = max(dp[c], dp[c - price] + value);
            }
        }
    }

    void multiple(int price, int value, int amount) {
        if (price * amount >= money) {
            complete(price, value);
        } else {
            for (int i = 1; amount > i;  i *= 2) {
                zero_one(price * i, value * i);
                amount -= i;
            }
            if (amount) {
                zero_one(price * amount, value * amount);
            }
        }
    }

    int solve(void) {
        return *max_element(dp, dp + money + 1);
    }
} backpack;

int tcase, n, m, p, h, c;

int main(int argc, char const *argv[]) {
#ifndef ONLINE_JUDGE
    freopen("wenchuan.txt", "r", stdin);
#endif

    scanf("%d", &tcase); while (tcase--) {
        scanf("%d %d", &n, &m);
        backpack.clear(n);
        for (int i = 0; m > i; ++i) {
            scanf("%d %d %d", &p, &h, &c);
            backpack.multiple(p, h, c);
        }
        printf("%d
", backpack.solve());
    }

    return 0;
}