Maximum Height by Stacking Cuboids
给一些砖块的长宽高, 可以旋转, 问怎么摆放可以有最高的高度, 求高度.
这个题虽然可以旋转, 但是其实因为限制: 必须完全小于长宽高的砖块才能放到另一个砖块上边. 所以没有旋转没有任何意义. 通过排序, 找到最长的, 然后再通过排序找到最大的. 即可做dp.
设dp[i]是包含砖块i作为可用砖块的最佳规划方案. 那么dp[i] = max{dp[j], where j < i and (i,j) meet requirements} 这个是bottom-up.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public int maxHeight(int[][] cuboids) { int n = cuboids.length; int[] dp = new int[n]; int res = 0; for(int[] c : cuboids){ Arrays.sort(c); } Arrays.sort(cuboids,(a,b) -> a[2] != b[2] ? b[2] - a[2] : a[1] != b[1] ? b[1] - a[1] : a[0] != b[0] ? b[0] - a[0]: 0); for(int i = 0; i < n; i++) { for(int j = 0; j < i; j++){ if(cuboids[i][0] <= cuboids[j][0] && cuboids[i][1] <= cuboids[j][1] && cuboids[i][2] <= cuboids[j][2]) { dp[i] = Math.max(dp[i], dp[j]); } } dp[i] += cuboids[i][2]; res = Math.max(res, dp[i]); } return res; } |