hdu1069

#include <iostream> #include <algorithm> #include <cstring> using namespace std; class Data { public: int S, Height; int upl, uph; }; Data Da[100]; int n; int dp[100]; int cmp(const Data &a, const Data &b) //按照面积最大或高度最高排序 { if(a.S != b.S) return a.S > b.S; else return a.Height > b.Height; } int main() { // freopen("data.txt", "r", stdin); int i, j, k, Case = 1; int a, b, c; while(cin >> n && n) { k = 0; memset(dp, 0, sizeof(dp)); for(i = 0; i < n; i++) //计算每一个面的面积，以及顶面的长宽以及高度 { cin >> a >> b >> c; Da[k].S = a * b; Da[k].upl = a > b ? a : b; Da[k].uph = a > b ? b : a; Da[k++].Height = c; Da[k].S = a * c; Da[k].upl = a > c ? a : c; Da[k].uph = a > c ? c : a; Da[k++].Height = b; Da[k].S = b * c; Da[k].upl = b > c ? b : c; Da[k].uph = b > c ? c : b; Da[k++].Height = a; } sort(Da, Da + k, cmp); //排序 int ans = 0; for(i = 0; i < k; i++) //动态规划 { dp[i] = Da[i].Height; for(j = 0; j < i; j++) { if(Da[i].S < Da[j].S && Da[i].upl < Da[j].upl && Da[i].uph < Da[j].uph) //判断是否符合 { dp[i] = dp[i] > dp[j] + Da[i].Height ? dp[i] : dp[j] + Da[i].Height; } } if(ans < dp[i]) //最大高度 ans = dp[i]; } cout << "Case " << Case++ << ": maximum height = " << ans << endl; } return 0; }