HDU - 1069 Monkey and Banana（LIS变形）

HDU - 1069

题意：

给你n种长方体，每种长方体有三个参数长宽高，每种数量不限，现在让你将长方体摞一块，要满足上方长方体的长和宽严格小于下方的，求最大高度。

分析：

这道题其实就是最长递增子序列LIS的变形，首先将同一个长方体不同摆放视为不同的，也就是一个长方体有6种方式，之后按长宽排序，接着就是求LIS的模板了，只要将递增改为递减即可，注意状态 转移方程：

$dp[i] = max(dp[i], dp[j] + block[i].h (0 &lt; j &lt; i))$dp[i]=max(dp[i],dp[j]+block[i].h(0<j<i))

分别代表两种状态：

• 将block[i]作为最底层
• 找到之前最大的dp[j]，并且可以保证block[i]可以放上去，就是长宽都符合要求，把block[i]放上去，

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define d(x) cout << (x) << endl
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e3 + 10;

struct node
{
	int l, w, h;
}block[N];

int dp[N];		//dp[i]代表0 ~ i最大能堆起的高度
int co = 1;	//情况数
int n, x, y, z, ans, cnt;
int pre[3];

bool cmp(node a, node b)	//按照l降序，l相同按照w降序
{
	if(a.l > b.l)
		return 1;
	if(a.l == b.l && a.w > b.w)
		return 1;
	return 0;
}
void in(int x,int y,int z){
	block[cnt].l = x;
	block[cnt].w = y;
	block[cnt++].h = z;
}
int main()
{
	while(scanf("%d", &n), n){
		ans = -INF;
		cnt = 0;
		for (int i = 0; i < n; i++){
			scanf("%d%d%d", &x, &y, &z);	//一共有6个不同的面
			in(x, y, z);
			in(y, x, z);
			in(x, z, y);
			in(z, x, y);
			in(y, z, x);
			in(z, y, x);
		}
		sort(block, block + cnt, cmp);
		for(int i = 0; i < cnt; i++){
			dp[i] = block[i].h;			//初始化dp数组，最开始就是将block[i]放在最下面
			for (int j = 0; j < i; j++){
				if(block[j].l > block[i].l && block[j].w > block[i].w){
					dp[i] = max(dp[i], dp[j] + block[i].h);
				}
			}
			ans = max(ans, dp[i]);
		}
		printf("Case %d: maximum height = %d\n", co++, ans); 
	}
	return 0;
}