這題想超久，以後要再練一次

題目說明

如何用箱子堆出最高的塔
題目會給箱子有幾種(數量無限)，可翻轉箱子
每次疊的時候，長與寬皆須嚴格遞減
最後輸出最高的高度

解法

翻轉後有6種組合

(x, y, z)
(x, z, y)
(y, x, z)
(y, z, x)
(z, x, y)
(z, y, x)

使用LIS找
一開始一直掉進LIS找最長序列的陷阱去
但是!最多box(序列最長)不一定等於最高
所以不能完全套用LIS

LIS

LIS有兩個重點

1. 是由小排到大嗎?
2. 加入後是否能讓序列變長?

以此題來說要轉換一下思路

1. 是由大排到小嗎? (b1.W > b2.W && b1.L > b2.L)
2. 加入後是否能讓高度變大?

找的順序

//using LIS
//先從最底的box放(i=0)
for(int i=0;i<boxes.size();++i){
    	if(!HEIGHT[i]) HEIGHT[i] = boxes[i].H; //如果為0的話就初始本身高度
	//再找能放在i上面的box，因為i以前的box不可能放在i上面(都比較大)，所以可以從i+1找  
	for(int j=i+1;j<boxes.size();++j){
		if( (boxes[j].L < boxes[i].L) && 
			(boxes[j].W < boxes[i].W) && 
			(HEIGHT[i]+boxes[j].H > HEIGHT[j]) ){ //如果加入後能讓高度變大
			 HEIGHT[j] = HEIGHT[i]+boxes[j].H;
		}
	}
    	//後面到這裡基本上就全算完了，直接找最大值 
    	if(HEIGHT[i] > max) max = HEIGHT[i];
}