直接套用DAG的思路就行。
AC代码:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int INF=1<<30; const int maxn=50; int dp[maxn][3]; int G[maxn][3][maxn][3]; struct node{ int a[3],b[3],c[3]; node(){} node(int x,int y,int z){ a[0]=x,b[0]=y,c[0]=z; a[1]=x,b[1]=z,c[1]=y; a[2]=y,b[2]=z,c[2]=x; } }; int n; node u[maxn]; int solve(int i,int p){ //表示第i个格子p在顶面 if(dp[i][p]!=-1) return dp[i][p]; int t=u[i].c[p]; //高度 dp[i][p]=t; for(int j=0;j<n;++j){ for(int k=0;k<3;++k){ if(G[i][p][j][k]) dp[i][p]=max(dp[i][p],solve(j,k)+t); } } return dp[i][p]; } int main(){ int kase=1; while(scanf("%d",&n)==1&&n){ memset(G,0,sizeof(G)); memset(dp,-1,sizeof(dp)); int a,b,c; for(int i=0;i<n;++i){ scanf("%d%d%d",&a,&b,&c); u[i]=node(a,b,c); } for(int i=0;i<n;++i) for(int j=0;j<n;++j){ for(int k=0;k<3;++k) for(int h=0;h<3;++h){ if(u[i].a[k]>u[j].a[h]&&u[i].b[k]>u[j].b[h]||u[i].a[k]>u[j].b[h]&&u[i].b[k]>u[j].a[h]) G[i][k][j][h]=1; } } //枚举起点 int ans=-INF; for(int i=0;i<n;++i){ ans=max(ans,solve(i,0)); ans=max(ans,solve(i,1)); ans=max(ans,solve(i,2)); } printf("Case %d: maximum height = %d\n",kase++,ans); } return 0; }
如有不当之出欢迎指出!