UVA 10051

先將立方體按重量從大到小排序，然後就轉成了類似於最長上升子序列的問題；

定義狀態dp[i][j]表示以第i個立方體的第j面作為頂面時的最大高度。

則dp[i][j]=max(dp[k][d]+1;1<=k<=i-1,m[i][5-j]==m[d][k])

注意為了方便後面的狀態判定，我們在輸入的時候要使得相對的面的坐標和為一個常數5.

對於路徑輸出,我們可以采用記錄父節點的方法。

代碼如下：

#include
#include
#include
using namespace std;

int m[550][10],dp[550][10];
int n,Case;
string face[]={"front","left","top","bottom","right","back"};

typedef struct
{
    int x,y;
}F;
F fa[550][550];

void input()
{
    for(int i=n;i>=1;i--)
    {
        for(int j=0;j<=2;j++)
        {
            scanf("%d",&m[i][j]);
            scanf("%d",&m[i][5-j]);
        }
    }
}

void print(int ans,int x,int y)
{
    printf("Case #%d\n",++Case);
    printf("%d\n",ans);
    while(x!=-1&&y!=-1)
    {
        printf("%d ",n-x+1);
        cout<ans)
             ans=dp[i][j],x=i,y=j;
      }
    print(ans,x,y);
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        if(!n)
           break;
        if(Case!=0)
          printf("\n");
        input();
        solve_dp();
    }
  return 0;
}