Thursday, October 16, 2014

a bit of dp: SPOJ - BABTWR

Problem Statement:

Given N (N<30) types of 3D boxes with dimension x,y,z, find the maximum height of tower can be formed by stacking those boxes together with the condition:
1. each type of box can be used as many times as possible
2. if a box is stacked on top of another, its baselines must be smaller than the one below.

Rather than building the boxes one by one, we make use of the property that the boxes can be arranged in sorted order. Hence once we derived a suitable order of boxes that can be exploited, we perform a procedure similar to one in LIS to find the maximum height possible.

/* Idea:
Bottom Up: sort all boxes and possible orientations in terms of width and height.
WLOG width < height, hence comparison can be done between widths and heights exclusively.
Then do checks similar to LIS

vector<pair<pair<int,int>,int> > stack;
int box[33][3];
int dp[99];
int N;

int main(){
    while(cin >> N, N!=0){
        for(int i=0;i<N;++i){
            for(int j=0;j<3;++j){
                cin >> box[i][j];
        for(int i=0;i<N;++i){
            for(int j=0;j<3;++j){
                int a = box[i][j];
                int b = box[i][(j+1)%3];
                int c = box[i][(j+2)%3];
                if(a>b) swap(a,b);
        sort(stack.begin(), stack.end());
        dp[0] = stack[0].second;
        int ans = 0;
        for(int i=1;i<3*N;++i){
            int h = stack[i].first.first;
            int w = stack[i].first.second;
            dp[i] = 0;
            for(int j=i-1;j>=0;--j){
                int ch = stack[j].first.first;
                int cw = stack[j].first.second;
                if(ch < h && cw < w) dp[i] = max(dp[i], dp[j]);
            dp[i] += stack[i].second;
            ans = max(ans, dp[i]);
        cout << ans << endl;
    return 0;