a bit of dp: SPOJ - BABTWR

Problem Statement:
SPOJ - BABTWR

Summary:
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.

Solution:
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){
        stack.clear();
        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);
                stack.push_back(make_pair(make_pair(a,b),c));
            }
        }
        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;
}