UVA Tower of Cubes(10051)

题目大意：

       有N个立方体，立方体的6个面颜色不一，现在要求立方体按照体重从小到大叠起来，并且两个立方体接触面的颜色必须相同，求最高能叠多高？

 

解题思路：

       动态规划，本质上就是求最长递增子序列，同时加上了限制条件，就是两个立方体之间颜色要一样，所以我就先用动态规划求出最长符合要求的子序列的长度，同时记录序列最后一个元素的位置，然后再用递归输出子序列。求最长递增子序列的状态转移方程就不写了，直接看代码里面就有，就那么一行，主要就是在状态转移的时候加上判断条件，判断颜色是否一样，然后记录子序列最后一个元素用来递归用。递归的时候也一样，先要判断颜色。

 

代码：

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;

vector<int> temp;
vector< vector<int> > v;
int dp[510][6];
char director[6][7]={"front", "back", "left", "right", "top", "bottom"};

void printPath(int ans, int pos, int posK)
{
	if( ans <= 0 )
	{
		cout<<pos+1<<" "<<director[posK]<<endl;
		return ;
	}

	for( int j = pos-1; j >= 0; j-- )
	{
		for( int k = 0; k < 6; k++ )
		{
			if( v[pos][posK] == v[j][k] && dp[j][k%2?k-1:k+1]+1 == ans && ans >= 0  )
			{
				ans--;
				printPath( ans, j, k%2?k-1:k+1 );
				cout<<pos+1<<" "<<director[posK]<<endl;
				return;
			}
		}
	}
	return;
}

int main()
{
	freopen("test.txt", "r", stdin );

	int N, color;
	int T = 1;
	while( cin>>N, N )
	{
		memset( dp, 0, sizeof( dp ) );
		memset( path, -1, sizeof( path ) );
		for( int i = 0; i < N; i++ )
		{
			for( int j = 0; j < 6; j++ )
			{
				cin>>color;
				temp.push_back(color);
			}
			v.push_back(temp);
			temp.clear();
		}
		int ans = 0, pos, posK, tempH = 0; 
		for( int i = 1; i < N; i++ )
		{
			for( int j = 0; j < i; j++ )
			{
				for( int k = 0; k < 6; k++ )
				{					
					for( int h = 0; h < 6; h++ )
					{
						tempH = h%2?h-1:h+1;   //求出h面的另一面
						if( v[i][k] == v[j][h] )
						{
							dp[i][k] = max(dp[j][tempH]+1,dp[i][k]);								
							if( dp[i][k] > ans )
							{
								ans = dp[i][k];
								pos = i;  //记录最后一个立方体的位置
								posK = k;//记录最后一个立方体朝上的那个面
							}
						}
					}
				}
			}
		}
		
		int test = 1;
		cout<<"Case #"<<T<<endl<<ans+1<<endl;

		printPath(ans, pos, posK);

		cout<<endl;
		v.clear();
		T++;
	}

	return 0;
}