UVa 437 DAG 动态规划

#include <bits/stdc++.h>
using namespace std;
const int maxn = 35;
int d[maxn][5],c[maxn][5];
int n;

void get_dimensions(int v[],int b,int dim)
{
	int index=0;
	for(int i=0;i<3;i++)
		if(i!=dim) v[index++]=c[b][i];
}
int dp(int x,int y)
{
	int &ans = d[x][y];
	if(ans) return ans;
	int u[3],v[3];
	get_dimensions(u,x,y);
	for(int i=0;i<n;i++)
		for(int j=0;j<3;j++)
		{
			get_dimensions(v,i,j);
			if(u[0]>v[0]&&u[1]>v[1])	
				an***ax(dp(i,j),ans);
		}
	ans+=c[x][y];
	return ans;
}
int main()
{
	int kase=1;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0) return 0;
		int ans=0;
		memset(d,0,sizeof(d));
		for(int i=0;i<n;i++)
		{
			scanf("%d%d%d",&c[i][0],&c[i][1],&c[i][2]);
			sort(c[i],c[i]+3);
		}
		for(int i=0;i<n;i++)	
			for(int j=0;j<3;j++)
				an***ax(dp(i,j),ans);
		printf("Case %d: maximum height = %d\n",kase++,ans);
	}

	return 0;
}