Monkey and Banana

解题思路
因为每个长方形可以使用无数次，因此可以将一个长方形当做三个长方形来看待。首先按照长和宽从小到大排序。
dp思路，dp[i] 代表以第i个长方形为底时的最大高度。因此dp很容易想到就是从前面小的长方形中选择一个符合条件的长方形放在dp[i]上面,取其中最大值的情况。由于前dp[i] 已经在前面求解出来了，所以遍历一遍 max_H = max(max_H, dp[j]) 就能求出最大值。dp[i] = A[i].H + max_H; 在加上当前的长方形高度就是 以第i个长方形为底的最大高度。

#include <iostream>
#include <algorithm>
//#include <bits/stdc++.h>
using namespace std;

#define max(x, y)   (x>y?x:y)
#define min(x, y)   (x<y?x:y)

struct node
{
    int L;
    int W;
    int H;

    bool operator < (const struct node &A)
    {
        if(this->L == A.L)
            return this->W < A.W;

        return this->L < A.L;
    }
};


typedef struct node Node;

Node A[200];
int dp[200];
int N;

int main(int argc, char *argv[])
{
 
 //   freopen("G:\\data.txt", "r", stdin);

    int T = 0;

    while(cin >> N, N)
    {
        int l,w,h;
        int len = 0;

        memset(A, 0, sizeof(A));

        for(int i = 0; i < N; i++)
        {
            cin >> l >> w >> h;

            A[len].H = l; A[len].L = max(w, h); A[len++].W = min(w, h);
            A[len].H = w; A[len].L = max(l, h); A[len++].W = min(l, h);
            A[len].H = h; A[len].L = max(w, l); A[len++].W = min(w, l);
        }

        sort(A, A+len);

//        for(int i = 0; i < len; i++)
//        {
//            cout << A[i].L << " " << A[i].W << " " << endl;
//        }

        dp[0] = A[0].H;             //代表以A中第i个长方形为低时的最大高度

        int max_H;

        for(int i = 1; i < len; i++)
        {
            max_H=0;

            for(int j = 0; j < i; j++)
            {
                if(A[j].L < A[i].L && A[j].W < A[i].W)
                    max_H = max(max_H, dp[j]);	//从前面已经求出的情况中选择一个最大的
            }

            dp[i] = A[i].H + max_H;		//加上当前长方形的高度
        }
        cout << "Case "<< ++T << ": maximum height = ";
        cout << *max_element(dp, dp+len) << endl;
    }

    return 0;
}