动态规划（二）

#include<iostream>#include<cstring>#include<algorithm>using namespace std;#define maxn 92int dp[maxn], dps[maxn];int G[maxn][maxn];int k;int x[maxn], y[maxn];int dp_find(int i){    int& ans = dps[i];    if (ans > 0) return ans;    ans = dp[i];    for (int j = 0; j < k; j++){        if (G[i][j]){            ans = max(ans, dp_find(j) + dp[i]);        }    }    return ans;}int main(){    int T, kase;    kase = 0;    while (scanf("%d",&T)!=EOF&&T){        int a[3];        int  ans; k = 0;        for (int j = 0; j < T; j++){            cin >> a[0] >> a[1] >> a[2];            for (int i = 0; i < 3; i++){                dp[k] = a[i];                if (a[(i + 1) % 3] < a[(i + 2) % 3]){                    x[k] = a[(i + 1) % 3];                    y[k] = a[(i + 2) % 3];                }                else{                    x[k] = a[(i + 2) % 3];                    y[k] = a[(i + 1) % 3];                }                k++;            }        }        memset(G, 0, sizeof(G));        for (int i = 0; i < k;i++)            for (int j = 0; j < k; j++){                if (x[i] < x[j] && y[i] < y[j]){                                        G[i][j] = 1;                }        }        memset(dps, 0, sizeof(dps));        ans = 0;        for (int i = 0; i < k; i++){            if (dp_find(i)>ans)                ans = dp_find(i);        }        printf("Case %d: maximum height = %d\n", ++kase, ans);    }    return 0;}