UVA 10051 Tower of Cubesブロックの塔類LIS DP

题意:n個のブロックの各面の色を与えて、しかも与えたブロックの重さは増加して、ブロックを畳む时、重いブロックは下に置いて、接触する面の色は必ず同じで、最も长くいくつかのブロックを畳むことができることを求めます.
タイトルはLISに似ていて、LISで作ることができて、判断する时にいくつかの色の判断が多くなったので、直接1つのブロックを6つの状态に分けて、それぞれ上を向いています.
そしてLISと差が少ない方法で作ります.
コード:

/*
*  Author:      illuz <iilluzen[at]gmail.com>
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        uva10051.cpp
*  Create Date: 2013-11-07 15:39:55
*  Descripton:  dp 
*/

#include <cstdio>
#include <cstring>

const int MAXN = 3010;

char up[6][10] = {"front", "back", "left", "right", "top", "bottom"};
int dp[MAXN], path[MAXN], color[6];
int m, n;

struct Cube {
	int top, bot;
	int wei, pos;
	Cube() { };
	Cube(int t, int b, int w, int p) {
		top = t; bot = b; wei = w; pos = p;
	}
} c[MAXN]; 

void print(int p) {
	if (p == -1) return;
	print(path[p]);
	printf("%d %s
", c[p].wei, up[c[p].pos]);
}

int main() {
	int cas = 0;
	while (scanf("%d", &n) && n) {
		m = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 6; j++)
				scanf("%d", &color[j]);
			for (int j = 0; j < 6; j++)
				if (j % 2)
					c[m++] = Cube(color[j], color[j - 1], i + 1, j);
				else
					c[m++] = Cube(color[j], color[j + 1], i + 1, j);
		}

		memset(dp, 0, sizeof(dp));
		memset(path, -1, sizeof(path));
		for (int i = 0; i < m; i++)
			for (int j = i + 1; j < m; j++)
				if (c[i].wei < c[j].wei && c[i].bot == c[j].top && dp[j] < dp[i] + 1) {
					dp[j] = dp[i] + 1;
					path[j] = i;
				}

		int ans = 0, p = 0;
		for (int i = 1; i < m; i++)
			if (ans < dp[i])
				ans = dp[i], p = i;

		if (cas)
			printf("
");
		printf("Case #%d
%d
", ++cas, ans + 1);
		print(p);
	}
	return 0;
}