uva 10051(最長上升子序列)

題意：有n個正方體，從1到n的重量以此上升，且每個正方體每一面有特定的顔色，要求把正方體壘起來保證下面的重量都比上面的重，且下面的正方體的頂部的顔色和和這個正方體緊鄰的上面的正方體的底部的顔色應該是相同的，輸出這個壘起來的正方體最多能有幾個，且頂部的顔色是什麼。

題解：先把每個正方體根據頂部顔色可以有6種一共分成6個正方體，然後用最長上升子序列的算法将長度更新，并且用一個link數組将和自己相連的正方體序号存起來，最後遞歸列印這條路。

#include <stdio.h>
#include <string.h>
const int N = 3005;
struct Cube {
	int b, t, w; 
}cube[N];
int n, t = 1, num, f[N], link[N];
const char str[6][8] = {"front", "back", "left", "right", "top", "bottom"};

void print(int cur) {
	if (f[cur] == 1) {
		printf("%d %s\n", cube[cur].w, str[cur % 6]);
		return;
	}
	print(link[cur]);
	printf("%d %s\n", cube[cur].w, str[cur % 6]);
}

int main() {
	while (scanf("%d", &n) && n) {
		num = 0;
		int a, b;
		for (int i = 1; i <= n; i++)
			for (int j = 0; j < 3; j++) {
				scanf("%d%d", &a, &b);
				cube[num].b = b;
				cube[num].t = a;
				cube[num++].w = i;
				cube[num].b = a;
				cube[num].t = b;
				cube[num++].w = i;
			}
		int maxx = -1, k;
		memset(link, -1, sizeof(link));
		for (int i = 0; i < num; i++) {
			f[i] = 1;
			for (int j = 0; j < i; j++) {
				if (cube[i].w > cube[j].w && cube[i].t == cube[j].b && f[i] < f[j] + 1) {
					link[i] = j;
					f[i] = f[j] + 1;
				}
			}
			if (maxx < f[i]) {
				maxx = f[i];
				k = i;
			}
		}
		if (t != 1)
			printf("\n");
		printf("Case #%d\n", t++);
		printf("%d\n", maxx);
		print(k);
	}
	return 0;
}