程式碼備份區

題意：

給很多個六面體他不同面的顏色(數字)，六面體會按照重量排序(由1~n)

問說如果要把這些六面體疊起來，而且連接的那邊顏色要相同，最多可以疊幾層

解法：

把每個六面體拆成六種情況(上下左右前後在上面的情形)

然後去做最長路徑dp(因為是DAC所以可以longest path)，即可得到解

程式碼：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int n;
char color[6][12] = {"front","back","left","right","top","bottom"};

int dp[3003];
int bot[3003];
int top[3003];
int pre[3003];

void printPath(int now){
    if(now == -1)return ;
    printPath(pre[now]);
    printf("%d %s\n",now/6+1,color[now%6]);
}

int main(){
    int i,j;
    int c[6];
    int tmp;
    int Case =  0;
    while(scanf(" %d",&n)!=EOF&&n){
        if(Case)puts("");
        for(i=0;i<n;++i){
            for(j=0;j<6;++j){
                scanf("%d",&c[j]);
            }
            for(j=0;j<6;++j){
                tmp = i*6+j;
                top[tmp] = c[j];
                bot[tmp] = (j%2)?c[j-1]:c[j+1];
                dp[tmp] = 1;
                pre[tmp] = -1;
            }
        }
        n = n*6;
        tmp = 0;
        for(i=0;i<n;++i){
            if(dp[tmp]<dp[i])tmp = i;
            for(j=((i/6)+1)*6;j<n;++j){
                if(top[j]==bot[i] && dp[j]<dp[i]+1){
                    dp[j] = dp[i]+1;
                    pre[j] = i;
                }
            }
        }
        printf("Case #%d\n%d\n",++Case,dp[tmp]);
        printPath(tmp);
    }
    return 0;
}