题目链接

Space Elevator POJ - 2392

思路

$$ \begin{aligned}大小有限制的多重背包，先排序再dp。\end{aligned} $$

时间复杂度

$$ O(K * max({a_i})) $$

代码

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXK = 400 + 10;
const int MAXN = 4e4 + 10;

int h[MAXK], a[MAXK], c[MAXK], id[MAXK];
int dp[MAXN];

bool cmp(int x, int y) {
    return a[x] < a[y];
}

int main() {
    int k;
    scanf("%d", &k);// don't forget &
    for (int i = 1; i <= k; i++) {
        scanf("%d%d%d", &h[i], &a[i], &c[i]);// don't forget &
        id[i] = i;
    }
    sort(id + 1, id + 1 + k, cmp);

    memset(dp, -1, sizeof dp);
    dp[0] = 1;
    for (int i = 1; i <= k; i++) {
        int x = id[i];
        for (int j = 0; j <= a[x]; j++) {
            if (dp[j] >= 0) {
                dp[j] = c[x];
            } else if(j - h[x] >= 0 && dp[j - h[x]] > 0){
                dp[j] = dp[j - h[x]] - 1;
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= 40000; i++) {
        if (dp[i] != -1) {
            ans = i;
        }
    }
    printf("%d", ans);
    return 0;
}