#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class mycompare
{
public:
    bool operator()(const vector<int>& box1, const vector<int>& box2)
    {
        return box1[0]==box2[0]?(box1[1]==box2[1]?(box1[2]<=box2[2]):box1[1]<box2[1]):box1[0]<box2[0];
    }
};
int main()
{
    int n;
    cin>>n;
    vector<vector<int>> boxes(n,vector<int>(3,0));
    for(int i=0;i<n;++i) for(int j=0;j<3;++j) cin>>boxes[i][j];
    // for(int i=0;i<n;++i) for(int j=0;j<3;++j) cout<<boxes[i][j]<<" ";
    // 动规dp ， 这里的dp[i]指的是当前为止 最大的高度
    sort(boxes.begin(),boxes.end(),mycompare());
    vector<int> dp(n,0);
    for(int i=0;i<n;++i)
    {
        dp[i] = boxes[i][2];
        for(int j=0;j<i;++j)
        {
            if(boxes[i][0]>boxes[j][0] && boxes[i][1]>boxes[j][1] && boxes[i][2]>boxes[j][2])
            {
                dp[i] = max(dp[i],dp[j]+boxes[i][2]);
            }
        }
    }
    cout<<*max_element(dp.begin(),dp.end());
    return 0;
}

N = int(input())
box = [list(map(int,input().split())) for _ in range(N)]
box.sort(key = lambda x:(x[0],x[1],x[2]))
dp = [0]*N
for i in range(N):
    dp[i]=box[i][2]
    for j in range(i):
        if box[j][0]<box[i][0] and box[j][1]<box[i][1] and box[j][2]<box[i][2]:
            dp[i]=max(dp[i],dp[j]+box[i][2])
print(max(dp))

递交一个输入方法简单的代码

def can_stack(box1,box2):
    return box1[0] > box2[0] and box1[1] > box2[1] and box1[2] > box2[2]
def max_height(boxes,n):
    dp = [0] * (n+1)
    for i in range(1,n+1):
        dp[i] = boxes[i][2]
        for j in range(1,i):
            if can_stack(boxes[i],boxes[j]):
                dp[i] = max(dp[i],dp[j]+boxes[i][2])
    return max(dp)
def main():
    n = int(input())
    boxes = [(0,0,0)]
    for _ in range(n):
        boxes.append(tuple(map(int,input().split())))
    boxes.sort(key=lambda x:(x[0],x[1],x[2]))
    ans = max_height(boxes,n)
    print(ans)
if __name__ == "__main__":
    main()

我貌似想复杂了，解法是动规，dp[i][j][k][s]代表前i个盒子，以j长、k宽、s高结尾的最大堆起来的高度

Java代码

import java.lang.*;
import java.util.*;
class Node{
    // a,b,c是长宽高，d仅作为区分性id防止去重
    int a,b,c,d;
    Node(int a,int b,int c,int d){
        this.a = a;
        this.b = b;
        this.c = c;
        this.d = d;
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Node [] nodes = new Node[n];
        for(int i = 0;i<n;i++){
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            nodes[i] = new Node(a,b,c,i);
        }
        Arrays.sort(nodes, new Comparator<Node>(){
            public int compare(Node n1,Node n2){
                if(n1.a!=n2.a)
                    return n1.a-n2.a;
                if(n1.b!=n2.b)
                    return n1.b-n2.b;
                if(n1.c!=n2.c)
                    return n1.c-n2.c;
                return n1.d-n2.d;
            }
        });
        int [][][][]dp = new int [n+1][11][11][11];
        // dp[i][j][k][s]代表前i个盒子以j长、k宽、s高结尾所能堆的最高高度
        int max = 0;
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=10;j++){
                for(int k = 1;k<=10;k++){
                    for(int s = 1;s<=10;s++){
                        dp[i][j][k][s] = dp[i-1][j][k][s];
                    }
                }
            }
            int x = nodes[i-1].a;
            int y = nodes[i-1].b;
            int z = nodes[i-1].c;
            for(int j = 0;j<x;j++){
                for(int k = 0;k<y;k++){
                    for(int s = 0;s<z;s++){
                        dp[i][x][y][z] = Math.max(dp[i][x][y][z], dp[i-1][j][k][s]+nodes[i-1].c);
                            max = Math.max(max, dp[i][x][y][z]);
                    }
                }
            }
        }
        System.out.println(max);
    }
}

题面描述；

在圣诞节到来之际，小塔的妈妈准备了多种尺寸的圣诞礼盒，小塔想通过堆叠这些礼盒来获得尽可能高的堆叠高度。每个礼盒的尺寸由长、宽、高三个值组成。小塔的任务是将礼盒堆叠起来，要求底部的礼盒必须在长、宽、高三个维度上均大于上面的礼盒（不允许相等）。现在，我们需要帮助小塔计算出最高的堆叠高度。

输入格式如下：第一行包含一个整数N，表示礼盒的个数。接下来的N行，每行包含三个整数，分别表示一个礼盒的长、宽和高。礼盒的数量不超过1000个，且每个盒子的长、宽、高的取值范围为1到10。

输出格式要求输出一行，表示能够堆出盒子的最高高度。

思路：动态规划

将所有盒子按照长、宽、高的三个优先级进行从小到大的排序，那么后面的盒子一定不可能放在前面盒子的上面。所以我们排序之后，选择的顺序就已经是定死的从左往右选择了。那么可以使用动态规划进行求解。

定义$dp[i]$表示放上第$i$个盒子所能达到的最大高度，则有 dp[i] = max{ dp[j] + height[i] ,mid j < i, wide[j] < wide[i], length[j] < length[i] }

答案为$max{dp[i]},1\le i\le n$

题目分析

在这个问题中，我们需要堆叠一些圣诞礼盒，以获得尽可能高的堆叠高度。每个礼盒的尺寸由长、宽和高三个值组成。在堆叠时，下面的盒子必须在长、宽和高的所有维度上都大于上面的盒子。通过合理的选择和排列，可以达到最佳的高度。

解题思路

1. 排序：首先，将所有盒子按照长、宽、高三个维度进行从小到大的排序。由于后面的盒子在长、宽、高方面都大于前面的盒子，因此可以确保一个盒子不会被放在另一个盒子上面，从而简化了问题。

2. 动态规划：接下来，使用动态规划来解决问题。定义 dp[i] 表示以第 i 个盒子为顶部盒子时，所能达到的最大堆叠高度。我们需要考虑所有之前的盒子，如果一个盒子可以放在另一个盒子上面，就更新 dp[i] 的值。

3. 结果计算：最终，结果为所有 dp[i] 中的最大值，即为我们能够堆叠的最高高度。

代码

java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int n;
    static int[] dp;
    static Box[] box;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        box = new Box[n + 1];
        dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            box[i] = new Box(sc.nextInt(), sc.nextInt(), sc.nextInt());
        }

        Arrays.sort(box, 1, n + 1, (a, b) -> {
            if (a.l != b.l) {
                return a.l - b.l;
            }
            if (a.w != b.w) {
                return a.w - b.w;
            }
            return a.h - b.h;
        });

        int ans = 0;
        for (int i = 1; i <= n; i++) {
            dp[i] = box[i].h;
            for (int j = 1; j < i; j++) {
                if (box[i].h > box[j].h && box[i].l > box[j].l && box[i].w > box[j].w) {
                    dp[i] = Math.max(dp[i], dp[j] + box[i].h);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        System.out.println(ans);
        sc.close();
    }

    static class Box {
        int l, w, h;

        Box(int l, int w, int h) {
            this.l = l;
            this.w = w;
            this.h = h;
        }
    }
}

python

N=int(input())
box=[]
for _ in range(N):
    box.append(list(map(int,input().split())))

box.sort(key=lambda x:(x[0],x[1],x[2])) #升序排序

dp=[0]*N #对于每个盒子作为最底层，其可以获得的最大高度是多少

for i in range(N):
    dp[i]=box[i][2] #是其自己的高度
    for j in range(i):
        #遍历前面的盒子
        #如果比前一个盒子的长宽高都大，那就是自己的高度再加上j盒子的最大高度
        if box[i][0]>box[j][0] and box[i][1]>box[j][1] and box[i][2]>box[j][2]:
            dp[i]=max(dp[i],dp[j]+box[i][2])

print(max(dp))

C++

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

const int maxn=1e3+10;
int dp[maxn];
int n;
struct node{
	int l, w, h;
}box[maxn];


int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
    	cin>>box[i].l>>box[i].w>>box[i].h;
	}
    //长、宽、高的三个优先级进行从小到大的排序
    sort(box+1, box+n+1, [&](node a, node b){
		if(a.l!=b.l){
			return a.l<b.l;   
		}
		if(a.w!=b.w){
			return a.w<b.w;
		}
		return a.h<b.h;
	});
    int ans=0;
    //dp[i]表示放上第i个盒子所能达到的最大高度
    for(int i=1;i<=n;++i){
        dp[i]=box[i].h;
        for (int j = 1; j < i; j++) {
            if (box[i].h > box[j].h && box[i].l > box[j].l && box[i].w > box[j].w) {
                dp[i]=max(dp[i],dp[j]+box[i].h);
            }
        }
        ans = max(ans,dp[i]);
    }
    cout<<ans;
}