Skip to main content

Maximum Height by Stacking Cuboids

由于 widthi <= widthj 且 lengthi <= lengthj 且 heighti <= heightj 的限制这道题的难度降低了很多,变成了一个简单的dpOn^2&On

#define Max(x, y) x>y?x:y
class Solution {public:    int maxHeight(vector<vector<int>>& cuboids) {        const int cuboidsize = cuboids.size();
        for(int i = 0; i < cuboidsize; i++) {            sort(cuboids[i].begin(), cuboids[i].end());        }        sort(cuboids.begin(), cuboids.end());        int dp[100];        memset(dp, 0, sizeof(int)*cuboidsize);
        int maxdp = 0;        for(int i = cuboidsize-1; i >= 0; i--) {            dp[i] = cuboids[i][2];            for(int j = i + 1; j < cuboidsize; j++) {                if(cuboids[i][0] <= cuboids[j][0]                 && cuboids[i][1] <= cuboids[j][1]                && cuboids[i][2] <= cuboids[j][2]) {                    dp[i] = Max(dp[i], cuboids[i][2] + dp[j]);                }            }            maxdp = Max(maxdp, dp[i]);        }                    return maxdp;    }};