uva 10051 Tower of Cubes题目大意：按重量给出N个木块六个面的颜色（前后左右上下），重量逐个增加。要求满足上面的木块底部颜色与他下方的木块顶部颜色相同，并且上面的木块要比下面的木块轻，，求最高可以垒几个木块。解题思路：把一个木块分成6个状态，就是一个最长上升子序列的问题。;ll;char dir[6][10] = {“front”, “back”, “left”, “right”, “top”, “bottom”}; struct Cub{int top, bot;int wei, pos;Cub() {};Cub(int t, int b, int w, int p) {top = t, bot = b, wei = w, pos = p;}}cub[N];int dp[N], rec[N], Case;void print(int p) {if (p == -1) return;print(rec[p]);printf(“%d %s\n”, cub[p].wei, dir[cub[p].pos]); } int main() {int n;Case = 0;while (scanf(“%d”, &n) != EOF, n) {int cnt = 0, color[6];for (int i = 1; i <= n; i++) {for (int j = 0; j < 6; j++) {scanf(“%d”, &color[j]);}for (int j = 0; j < 6; j++) {if (j % 2) {cub[cnt++] = Cub(color[j], color[j – 1], i, j);} else {cub[cnt++] = Cub(color[j], color[j + 1], i, j);}}}memset(dp, 0, sizeof(dp));memset(rec, -1, sizeof(rec));for (int i = 0; i < cnt; i++) {for (int j = i + 1; j < cnt; j++) {if (cub[i].wei < cub[j].wei && cub[i].bot == cub[j].top && dp[j] < dp[i] + 1) {dp[j] = dp[i] + 1;rec[j] = i;}}}int ans = 0, r;for (int i = 1; i < cnt; i++) {if (dp[i] > ans) {ans = dp[i];r = i;}}if (Case) {printf(“\n”);}printf(“Case #%d\n%d\n”, ++Case, ans + 1);print(r);}return 0;}
有多远，走多远，把足迹连成生命线。
