POJ 2392 : Space Elevator

蟻本の練習問題を消化中

概要

K種類のブロックがあって,i番目のブロックは高さhiであり,ci個だけある.また,ブロックの一部がhiを超えるとまずい.
ブロックを積み上げていくとき,到達できる高さの最大はいくつか.

解法

ブロックを高さ制限でソート.
dp[i][j]:=(高さjへ到達するために必要なブロックの最少数.不可能なら-1)
としてDPを行う.

struct Block{
    int h, a, c;
    Block(int h, int a, int c) : h(h),a(a),c(c) {}
    Block() {}
};
bool operator<(const Block &a, const Block &b){
    return a.a < b.a;
}
int K;
int dp[40010];
Block b[400];

int main(){
    scanf("%d", &K);
    for(int i = 0; i < K; ++i){
        int h, a, c;
        scanf("%d%d%d", &h, &a, &c);
        b[i] = Block(h, a, c);
    }
    sort(b, b + K);
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    for(int i = 0; i < K; ++i){
        for(int j = 0; j <= b[i].a; ++j){
            if(dp[j] >= 0) dp[j] = b[i].c;
            if(j >= b[i].h) dp[j] = max(dp[j], dp[j-b[i].h] - 1);
        }
    }
    int r;
    for(r = 40000; ; --r) if(dp[r] >= 0) break;
    printf("%d\n", r);
    return 0;
}