Think: 1知识点：基础dp 2题意：询问n种箱子在满足 1>可以不同面为底 2>一个叠一个 3>叠的箱子中上面的箱子长和宽都分别严格小于下面的箱子的长和宽 4>无限个箱子 条件下能够叠的最高高度
vjudge题目链接
以下为Accepted代码——基础dp
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct Node{ int x, y, z; int w; bool operator < (const Node &b) const{ return w < b.w; } }link[114]; int tp, dp[114]; /*dp[i]:表示前i个状态的最高高度*/ int main(){ int k = 1, n, i, j, x, y, z, ans, mv; while(scanf("%d", &n) && n){ tp = 0; for(i = 1; i <= n; i++){ scanf("%d %d %d", &x, &y, &z); link[tp].x = x, link[tp].y = y, link[tp].z = z, link[tp].w = max(x, y), tp++; link[tp].x = x, link[tp].y = z, link[tp].z = y, link[tp].w = max(x, z), tp++; link[tp].x = y, link[tp].y = z, link[tp].z = x, link[tp].w = max(y, z), tp++; } sort(link, link+tp); for(i = 0; i < tp; i++) dp[i] = link[i].z; ans = 0; for(i = 1; i < tp; i++){ mv = 0; for(j = i-1; j >= 0; j--){ if((link[i].x > link[j].x && link[i].y > link[j].y) || (link[i].x > link[j].y && link[i].y > link[j].x)){ if(mv < dp[j]) mv = dp[j]; } } dp[i] += mv; ans = max(ans, dp[i]); } printf("Case %d: maximum height = %d\n", k++, ans); } return 0; }