题解 | 堆箱子

#include <algorithm>
#include <tuple>
#include <vector>
class Box {
public:
    int getHeight(vector<int> w, vector<int> l, vector<int> h, int n) {
        // write code here
        vector<tuple<int,int,int>> boxes;    
        for(int i=0;i<n;++i){
            boxes.emplace_back(w[i],l[i],h[i]);
        }
        sort(boxes.begin(), boxes.end());
        vector<int> dp(n);
        int maxH=0;
        for(int i=0;i<n;++i){
            auto [wi,li,hi] = boxes[i];
            dp[i] =hi;
            for (int j=0; j<i; ++j) {
                auto [wj,lj,hj] = boxes[j];
                if(wj< wi && lj<li){
                    dp[i] = max(dp[i], dp[j]+hi);
                }
            }
            maxH = max(maxH, dp[i]);
        }
        return maxH;
        
    }
};