PKU 1972 Dice Stacking

http://poj.org/problem?id=1972

対面の和が7とは限らないサイコロを順番どおりにつみあげて、側面の数字の和を最大にするときの最大値を求めろというような問題。
ただし、積み上げるときは、上下のサイコロの同じ数字の面がくっつくようにする。

水平方向に自由に回転できるので、6通り全て試すだけ。

int dp[6][10000];
int max(int a,int b,int c,int d){
  return max(max(a,b),max(c,d));
}

void solve(){
  int n;
  cin >> n;
  int a,b,c,d,e,f;

  memset(dp,0,sizeof(dp));  

  for(int i=0;i<n;++i){
    int j=i+1;
    cin >> a >> b >> c >> d >> e >> f;
    --a,--b,--c,--d,--e,--f;
    dp[a][j]=dp[f][i]+max(b,c,d,e)+1;
    dp[b][j]=dp[d][i]+max(a,c,e,f)+1;
    dp[c][j]=dp[e][i]+max(a,b,d,f)+1;

    dp[f][j]=dp[a][i]+max(b,c,d,e)+1;
    dp[d][j]=dp[b][i]+max(a,c,e,f)+1;
    dp[e][j]=dp[c][i]+max(a,b,d,f)+1;
  }

  int ans=0;
  rep(i,6) ans=max(ans,dp[i][n]);
  cout << ans << endl;
}

main(){
  int t;
  cin >> t;
  rep(i,t) solve();
}