hdu 1069 Monkey and Banana 【动态规划】

题意：研究人员要测试猴子的IQ，将香蕉挂到一定高度，给猴子一些不同大小的箱子，箱子数量不限，让猩猩通过叠长方体来够到香蕉。现在给你N种长方体，要求：位于上面的长方体的长和宽要小于下面长方体的长和宽。

思路：对于一种长方体，长宽高（a,b,c）有6总不同的组成方式{（a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a) },对所有组成方式的长方体从小到大排序，比较满足长1<长2，宽1<宽2，的最大高度。

dp[i]: 表示第i个盒子的高 + 前i-1个盒子在满足(x1<x2,y1<y2)的情况下可以组成的最大的高度

#include <cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

const int Max = 200+10;

//dp[i]:表示第i个盒子的高+前i-1个盒子在满足(x1<x2,y1<y2)的情况下可以组成的最大的高

int dp[Max];

struct node{

	int x,y,z;

};

node no[Max];

int cmp(node a,node b)

{

	if(a.x==b.x) return a.y<b.y;

	else return a.x<b.x;

}

int main()

{

	int n,x,y,z;

	int Case =1;

	while(cin>>n)

	{

		if(n==0) break;

		int cnt = 0;

		for(int i=0;i<n;i++)

		{

			cin>> x >> y >>z;

			no[cnt].x = x,no[cnt].y=y,no[cnt++].z=z;

			no[cnt].x = x,no[cnt].y=z,no[cnt++].z=y;

			no[cnt].x = y,no[cnt].y=x,no[cnt++].z=z;

			no[cnt].x = y,no[cnt].y=z,no[cnt++].z=x;

			no[cnt].x = z,no[cnt].y=x,no[cnt++].z=y;

			no[cnt].x = z,no[cnt].y=y,no[cnt++].z=x;

		}

		sort(no,no+cnt,cmp);

		dp[0]=no[0].z;

		int maxh;

		for(int i=1;i<cnt;i++)

		{

			maxh=0;

			for(int j=0;j<i;j++)

			{

				if(no[j].x<no[i].x&&no[j].y<no[i].y)

					 maxh = max(maxh,dp[j]);;

			}

			dp[i] = no[i].z+maxh;

		}

		 maxh=0;

		for(int i=0;i<cnt;i++)

			if(dp[i]>maxh) maxh = dp[i];

		printf("Case %d: maximum height = %d\n",Case++,maxh);

	}

	return 0;

}

巴特西

hdu 1069 Monkey and Banana 【动态规划】

最新文章

热门文章