题目链接： 传送门
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 200010; int n, dp[N], ca = 1; //一个结构体用来存下砖头 struct Brick { int wid, len, he; } brick[N]; //对砖头进行排序 bool cmp(Brick x, Brick y) { return x.len == y.len ? x.wid < y.wid : x.len < y.len; } int main() { while(scanf("%d", &n)!=EOF) { if(n == 0) break; int a, b, c, idx = 0, ans = 0; //初始化 memset(brick, 0, sizeof(brick)); memset(dp, 0, sizeof(dp)); //输入砖头 for(int i = 1; i <= n; i++) { scanf("%d%d%d", &a, &b, &c); //因为砖头可以转动角度，所以这里把它的6种状态都存了下来 brick[idx++] = {a, b ,c}; brick[idx++] = {a, c, b}; brick[idx++] = {b, a, c}; brick[idx++] = {b, c, a}; brick[idx++] = {c, a, b}; brick[idx++] = {c, b, a}; } //对砖头进行排序 sort(brick, brick + idx, cmp); //接下来就与最长上升子序列相似了 for(int i = 0; i < idx; i++) { //记下第i块砖头高度 dp[i] = brick[i].he; for(int j = 0; j < i; j++) //如果当前砖符合要求的情况下，更新dp if(brick[i].len > brick[j].len && brick[i].wid > brick[j].wid) dp[i] = max(dp[i] , dp[j] + brick[i].he); } //找到所有序列中最长（这里是最高）的那个 for (int i = 0; i < idx; i++) ans = max(ans , dp[i]); //输出结果 printf("Case %d: maximum height = %d\n" , ca++ , ans); } return 0; }这道题可以用动态规划来做，其实这道题本质上是一道求最长公共子序列的加强版，建议先了解一下最长上升子序列如何用dp来求 相关题目 当你了解最长上升子序列如何求这道题就很好做了，首先讲一下数据的处理，因为砖头有长宽高，所以我们要开一个结构体来存储，又因为砖头可以转动所以要把所有情况枚举一遍（一共六种）。由于我们要尽可能拿更多，因此我们要进行排序，排序后拿去砖头才能保障拿到的是最优解。 数据讲完了，现在讲讲它与最长上升子序列的一些相似之处。首先结构上，枚举前i块砖头的最优拿法。dp[i]先记下第i块砖头高度，然后枚举前面每一个情况。然后这里的判断的结构与最长上升子序列相似，但是条件要复杂点，要求第i块砖头的长宽同时都要比第j块要大。接下来枚举完所有情况找到最大解即可。
