POJ-2392: Space Elevator

keyword

動的計画法　C++

問題概要

K(<400)種類のブロックがある。各ブロックはh(<100), a(<40000), c(<10)の値を持つ。hはブロック1個分の高さ、aは高さの限界値、cは個数である。ブロックを最大でどの高さまで積み上げることができるか求める問題。ただし、ブロックiの地面からの高さがa_iを越えてはいけない。

解法

aの小さい順に積み上げればよいことに気づけば簡単。小さい順に、到達可能な高さを配列で持っておけばよい。一応通した解法では計算量がO(K*log K + K*MAX_A*MAX_C)で通った(実装時間8分)けど、無駄が多いのでもう少し計算量を落とせそうな気がする。

#include <cstdio>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;

struct block{
    int h,a,c;
};

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

block bs[409];
bool visited[40009];
int K;

int solve(){
    sort(bs, bs+K);
    vector<int> cur, next;
    cur.push_back(0);
    for(int i=0; i<K; i++){
        next.clear();
        memset(visited, 0, sizeof(visited));
        for(int j=0; j<cur.size(); j++){
            int hh = cur[j];
            for(int k=0; k<=bs[i].c; k++){
                int nh = hh + bs[i].h*k;
                if(nh <= bs[i].a && !visited[nh]){
                    next.push_back(nh);
                    visited[nh] = true;
                }
            }
        }
        cur = next;
    }
    return *max_element(next.begin(), next.end());
}

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