本文主要是介绍UVA 437. 叠罗汉，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一堆正方体格子，每种格子有无限个，最高能叠多高。每一层的下面那个都必须严格大于上面那个（长和宽）
dp[i][j][k] 若有n个格子的话最多转移3*n次，懒得搞了...每一个都转移99次，反正n对多为30,。
dp[i][j][k]表示这是第i次转移，最上面那个是j，j的k面朝上。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;int cube[100][3];
int n;
int dp[100][100][3];
int a[3][2]={0,1,0,2,1,2};
int h[3]={2,1,0};
int area(int n,int k)
{return cube[n][a[k][0]]*cube[n][a[k][1]];
}
int height(int n,int k)
{return cube[n][h[k]];
}
int main()
{int cur;int next;int T=0;while(scanf("%d",&n)&&n!=0){for(int i=0;i<n;i++){for(int j=0;j<3;j++)scanf("%d",&cube[i][j]);}memset(dp,0,sizeof(dp));cur=0;next=1;for(int i=0;i<n;i++)for(int j=0;j<3;j++)dp[cur][i][j]=height(i,j);int flag=true;for(int ii=0;ii<100;ii++){flag=false;for(int i=0;i<n;i++){for(int j=0;j<3;j++){for(int k=0;k<n;k++){for(int l=0;l<3;l++){int minb=min(cube[i][a[j][0]],cube[i][a[j][1]]);int maxb=max(cube[i][a[j][0]],cube[i][a[j][1]]);int minu=min(cube[k][a[l][0]],cube[k][a[l][1]]);int maxu=max(cube[k][a[l][0]],cube[k][a[l][1]]);if(minb>minu&&maxb>maxu){dp[next][k][l]=max(dp[next][k][l],dp[cur][i][j]+height(k,l));flag=true;}else{dp[next][i][j]=max(dp[next][i][j],dp[cur][i][j]);}}}}}cur++;next++;}int max_=-1;for(int i=0;i<n;i++){for(int j=0;j<3;j++){if(max_<dp[99][i][j])max_=dp[99][i][j];}}printf("Case %d: maximum height = %d\n",++T,max_);}
}
这篇关于UVA 437. 叠罗汉的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
