Poj 2392: Space Elevator

poj2392.md

Poj 2392: Space Elevator

題目

分析

因為每種 blocks 有其高度限制，所以可以順勢想到：高度限制越低的 block 要越先疊。 將每種 blocks 根據高度限制（a），由小到大排序後，題目就變成了多重背包。

解多重背包，有兩種方法

###第一種

bool dp[i][v] = 可否使用前 i+1 種物品組出價值 v
dp[i][v] = any(dp[i-1][v - k * price[i]] | 0 <= k <= n[i])

在這題就是

bool dp[i][w] = 可否使用前 i+1 種 blocks 組出高度 w
答案是：最大的 m such that dp[K-1][m] is true)
dp[i][w] = any(dp[i-1][w - k * height[i]] | 0 <= k <= n[i])

複雜度為 O(K*max(a)*max(c))

###第二種 這種解法是從完全背包著手，請參這，複雜度可降至 O(K*max(a))

AC Code

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

using namespace std;

struct Block {
    int h;
    int a;
    int c;

    bool operator < (const Block& b) const {
        return a < b.a;
    }
};

int K;
Block blocks[400];

bool dp[400][40000+1];

int solve() {
    sort(blocks, blocks + K);

    for (int h = 0; h <= blocks[0].a; h += blocks[0].h)
        dp[0][h] = true;

    // dp[i][w] = any(dp[i-1][w - v[i] * k] | 0 <= k <= n[i])
    // => dp[i][w] = any(dp[i-1][w - k * blocks[i].h] | 0 <= k <= blocks[i].a)
    for (int i = 1; i < K; i++) {
        for (int w = 0; w <= blocks[i].a; w++) {
            for (int k = 0; k <= min(blocks[i].c, w / blocks[i].h); k++) {
                dp[i][w] |= dp[i-1][w - k * blocks[i].h];
            }
        }
    }

    for (int h = blocks[K-1].a; h >= 0; h--)
        if (dp[K-1][h])
            return h;
    return -1;
}

int main() {
    scanf("%d", &K);
    for (int i = 0; i < K; i++)
        scanf("%d %d %d", &blocks[i].h, &blocks[i].a, &blocks[i].c);
    printf("%d\n", solve());

    return 0;
}

AC Code (Optimized)

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

using namespace std;

struct Block {
    int h;
    int a;
    int c;

    bool operator < (const Block& b) const {
        return a < b.a;
    }
};

int K;
Block blocks[400];

bool dp[40000 + 1];
int num[40000 + 1];

int solve() {
    sort(blocks, blocks + K);

    dp[0] = true;
    for (int i = 0; i < K; i++) {
        memset(num, 0, sizeof(num));

        for (int j = blocks[i].h; j <= blocks[i].a; j++) {
            if (dp[j] == false && dp[j - blocks[i].h] &&
                num[j - blocks[i].h] < blocks[i].c) {
                dp[j] = true;
                num[j] = num[j - blocks[i].h] + 1;
            }
        }
    }

    for (int i = 40000; i >= 0; i--)
        if (dp[i])
            return i;

    return -1;
}

int main() {
    scanf("%d", &K);
    for (int i = 0; i < K; i++)
        scanf("%d %d %d", &blocks[i].h, &blocks[i].a, &blocks[i].c);
    printf("%d\n", solve());

    return 0;
}