z****8
发帖数: 5023 | 1 一堆方块 有H高 两个底 A1 A2
问你最高能堆多高MAX(SUM(H))
要求是上面一个方块的A1大于下面方块的A1 上面一个方块的A2大于下面方块的A2
方块不能倒下来放 也就是说A1 A2 H是固定的
求大牛解答 自己已经晕掉 不知道如何入手了 |
h**d
发帖数: 630 | 2 先sort by base_area即A1*A2
然后dp
递归公式
f[j] = max{f[i]}+Hj (i |
k****r
发帖数: 807 | 3 为什么sort by base_area呢？可不可以按A1sort然后dp呢？我试着练一下。create一
个class作为dp的内容including last X2 and current sumH
class dp {
int x2;
int sum;
}
public maxHeight(square[] s) {
sortSquareByA1(s); //sort by A1
int len = s.length;
int[][] dp = new int[len][s.len];
int result;
dp[0][0].sum = square[0].H;
dp[0][0].x2 = square[0].x2;
for(int i = 1; i < len; i++) { //add one more
if (square[i].A2 > square[i - 1].A2) {
dp[i][0].sum = dp[i - 1][0].sum + square[i].H;
} else {
dp[i][0].sum = square[i].H;
}
dp[i][0].x2 = square[i].x2;
}
for(int i = 1; i < len; i++) { //add nothing
dp[0][i].sum = dp[0][i-1].sum;
dp[0][i].x2 = dp[0][i-1].x2;
}
result = dp[0][0].sum;
for(int i = 1; i < len; i++) {
for(int j = 1; j < len - i; j++) {
if (square[i + j].A2 > dp[i - 1][j].x2) {
dp[i][j].sum = dp[i - 1][j].sum + square[i + j].H;
} else {
dp[i][j].sum = square[i + j].H;
}
dp[i][j].x2 = square[i + j].A2;
dp[i][j].sum = dp[i][j - 1].sum > dp[i][j].sum ? dp[i][j - 1].
sum : dp[i][j].sum;
dp[i][j].x2 = dp[i][j - 1].sum > dp[i][j].sum ? dp[i][j - 1].x2
}
result = dp[i][len - i - 1].sum > result ? dp[i][len - i - 1].sum :
result;
}
return result;
}
代码没有优化，不好看；
方法有点笨，还请指教。 |
z****8
发帖数: 5023 | 4 我也觉得是sort A1*A2 然后怎么弄就稀里糊涂晕菜了
【在 h**d 的大作中提到】
: 先sort by base_area即A1*A2
: 然后dp
: 递归公式
: f[j] = max{f[i]}+Hj (i
|
h**d
发帖数: 630 | 5 按A1或A2 sort也行 只要保证sort之后 可能符合要求的大的方块都是在小的方块后面
就行
【在 k****r 的大作中提到】
: 为什么sort by base_area呢？可不可以按A1sort然后dp呢？我试着练一下。create一
: 个class作为dp的内容including last X2 and current sumH
: class dp {
: int x2;
: int sum;
: }
: public maxHeight(square[] s) {
: sortSquareByA1(s); //sort by A1
: int len = s.length;
: int[][] dp = new int[len][s.len];
|
b******g
发帖数: 3616 | 6 A1, A2是底面两个边长吧？这是Cracking Code Interview recursion/dp那章的原题吧
。。。
【在 z****8 的大作中提到】
: 一堆方块 有H高 两个底 A1 A2
: 问你最高能堆多高MAX(SUM(H))
: 要求是上面一个方块的A1大于下面方块的A1 上面一个方块的A2大于下面方块的A2
: 方块不能倒下来放 也就是说A1 A2 H是固定的
: 求大牛解答 自己已经晕掉 不知道如何入手了
|
b******g
发帖数: 3616 | 7 sort by base area的原因是
当A1*A2 > B1*B2时，必然意味着A1>B1 || A2>B2，也就是说排除了A可以叠在B上面的
可能性。所以如果以base area排序以后。对于box B来说，排在它后面的所有盒子都无
法叠在它上面，而只需要检验排在它前面的那些盒子是否都符合两边同时小于B1 & B2。
这也就是为什么2楼大牛给的递推公式是：
f[j] = max{f[i]}+Hj (i
f[j]表示box j为最底下时的最大高度。依次检查排在j前(i
，如果A1i
box i为底的最大高度 f[i] + box j本身的高度 Hj。
如果sort by A1或A2道理也是一样的。
假如sort by A1，那么在检查candidate box i的时候，只要判断 A2i
【在 k****r 的大作中提到】
: 为什么sort by base_area呢？可不可以按A1sort然后dp呢？我试着练一下。create一
: 个class作为dp的内容including last X2 and current sumH
: class dp {
: int x2;
: int sum;
: }
: public maxHeight(square[] s) {
: sortSquareByA1(s); //sort by A1
: int len = s.length;
: int[][] dp = new int[len][s.len];
|
t*****3
发帖数: 112 | 8 没错，cc150用的是recursion + DP
【在 b******g 的大作中提到】
: A1, A2是底面两个边长吧？这是Cracking Code Interview recursion/dp那章的原题吧
: 。。。
|
h***s
发帖数: 45 | 9 CC第几章第几题呀，怎么没有看到CC有一章讲DP的？ |
l*****v
发帖数: 122 | 10 赞分析，明白了
B2。
i
【在 b******g 的大作中提到】
: sort by base area的原因是
: 当A1*A2 > B1*B2时，必然意味着A1>B1 || A2>B2，也就是说排除了A可以叠在B上面的
: 可能性。所以如果以base area排序以后。对于box B来说，排在它后面的所有盒子都无
: 法叠在它上面，而只需要检验排在它前面的那些盒子是否都符合两边同时小于B1 & B2。
: 这也就是为什么2楼大牛给的递推公式是：
: f[j] = max{f[i]}+Hj (i: f[j]表示box j为最底下时的最大高度。依次检查排在j前(i: ，如果A1i: box i为底的最大高度 f[i] + box j本身的高度 Hj。
: 如果sort by A1或A2道理也是一样的。
|
d*l
发帖数: 1810 | 11 两个底，不一样的话叫方块吗。题目都没有读懂：（
【在 z****8 的大作中提到】
: 一堆方块 有H高 两个底 A1 A2
: 问你最高能堆多高MAX(SUM(H))
: 要求是上面一个方块的A1大于下面方块的A1 上面一个方块的A2大于下面方块的A2
: 方块不能倒下来放 也就是说A1 A2 H是固定的
: 求大牛解答 自己已经晕掉 不知道如何入手了
|
g**********h
发帖数: 2 | 12 sort by A1， 然后对A2做longest increasing subsequence？ |
b******g
发帖数: 3616 | 13 思路就是这个思路。和longest increasing subsequence稍稍有点不一样,cc150上那道
马戏团人梯是用排序+longest increasing subsequence做的。这题的唯一区别是，每
个盒子有自己的高度，要求的不是最多能堆几个盒子，而是求最大高度。但也是换汤不
换药。只不过在算subsequence length的时候不是清点有几个盒子，而是清点所有可以
堆上去的盒子的总高度就行了。
【在 g**********h 的大作中提到】
: sort by A1， 然后对A2做longest increasing subsequence？
|
