monkey and banana.cpp

一个用到动态规划算法的acm题

/*
* NO        : ZOJ1093
* Name      : Monkey and banana.
* Create By : BEYONDER
* Date      : 2004-8-11-13:02.
* Method    : 动态规划。
*/
#include <iostream>

using namespace std;

struct Block
{
	int len;
	int wid;
	int hei;
	int max;
}block[100];
int n;
int max;
void swap( int & a, int & b )
{
	int temp = a;
	a = b;
	b = temp;
}
void init()
{
	for( int i = 0; i < 100; i ++ )
	{
		block[i].hei = 0;
		block[i].len = 0;
		block[i].max = 0;
		block[i].wid = 0;
	}
}
void solve( )
{
	int i, j;
	max = 0;
	for( i = 0; i < 3*n; i ++ )
			if( block[i].len < block[i].wid )
				swap( block[i].wid, block[i].len );

	for( i = 0; i < 3 * n; i ++ )
		for( j = i+1; j < 3*n; j ++ )//从大到小排序。
		{
			if( block[i].len > block[j].len 
				|| ( block[i].len == block[j].len && block[i].wid > block[j].wid ))//如果长相同，则以宽来比较。
			{
				swap( block[i].len, block[j].len );
				swap( block[i].wid, block[j].wid );
				swap( block[i].hei, block[j].hei );
			}
		}

	for( i = 0; i < 3 * n; i ++ )
		for( j = i+1; j < 3 * n; j ++ )
		{
			if( block[i].len < block[j].len && block[i].wid < block[j].wid )
			{
				if( block[j].max == 0 )
					block[j].max = block[i].max + block[i].hei; // 把block[i] 放在block[j]上所能达到的高度。
				else
					if( block[j].max < block[i].max + block[i].hei )
						block[j].max = block[i].max + block[i].hei;
			}
		}
	for( i = 0; i < 3 * n; i ++ )
	{
		if( block[i].max + block[i].hei > max )
			max = block[i].max + block[i].hei;
	}
	cout<<max<<endl;
}
int main()
{
	int i;
	int x,y,z;
	int Case = 0;
	while( cin>>n )
	{
		if( n == 0 )
			break;
		Case ++;
		init();
		max = 0;
		for( i = 0; i < n; i ++ )
		{
			cin>>x>>y>>z;

			block[i].len = x;
			block[i].wid = y;
			block[i].hei = z;
			block[i].max = 0;
			
			block[n+i].len = y;
			block[n+i].wid = z;
			block[n+i].hei = x;
			block[n+i].max = 0;

			block[2*n + i].len = z;
			block[2*n + i].wid = x;
			block[2*n + i].hei = y;
			block[2*n + i].max = 0;
		}
		cout<<"Case "<<Case<<": maximum height = ";

		solve();
	}
	return 0;
}