Dice Stacking

Dice Stacking

【题目概述】罗骰子游戏,N1<=N<=10)个骰子,每个骰子有六个编号为0~5的面,现在要求把骰子罗成一摞,且要求两个骰子重叠的面的编号相等,求罗成的长方体四个侧面中最大面积的侧面的面子。

 

 

 

 

 

 

 

 

 

 

 

【题目分析】将骰子罗列,求最大的侧面,还要求相邻两个骰子接触面编号相等?!该如何解决呢?看图,先来解决相邻的两个面编号相等的问题!有图得到  因此,可以很容易的判断一个面的对立面!第一个问题解决。

题目中给出了这个条件是狠重要就是,就是一个骰子可以左右转动,这提示我们水平的四个面中编号最大的面总是可以转到一个面上的。由此,我们可以确定那个面和其余骰子接触的时候,确定这个骰子提供的最大的面积。

确定这两个起初看是不确定的问题,下面的算法就是比较通俗的了。

 表示最大值,其中,i为已放入的骰子,第j个骰子的第k个面朝上。则

若只放一个筛子, , 其中b[i][j]表示第i个骰子的第j个面向上放置贡献的最大值,可以预处理的时候求出。

对于已放置的骰子,可以转移到为放置的上面,所以,枚举合法的状态,然后添加骰子,同时更新状态值。

【详细代码】下面是AC的代码。

//Name: pku_2596_Dice Stacking

#include <iostream>

using namespace std;

#define max(a, b)((a)=((a)>(b)?(a):(b)))

const int f[6]={5,4,3,2,1,0};

int a[10][10], b[10][10];

int dp[1<<10][10][6], n, ans;

int main() {

    //freopen("in.in", "r", stdin);

    int ca, i, j, k, p, q, t, kn;

    scanf("%d", &ca);

    while(ca-- && scanf("%d", &n)) {

        kn = 1<<n;

        memset(b, 0, sizeof(b));

        for(i = 0; i < n; i++) {

            for(j = 0; j < 6; j++) scanf("%d",a[i]+j);

            for(j = 0; j < 6; j++)

                for(k = 0; k < 6; k++) if(k!=j && k != f[j])

                    max(b[i][j], a[i][k]);

        }

        memset(dp, -1, sizeof(dp));

        for(i = 0; i < n; i++)

            for(j = 0; j < 6; j++) dp[1<<i][i][j] = b[i][j];

        for (i = 0; i < kn; i++) {

            for (j = 0; j < n; j++) {

                for (k = 0; k < 6; k++) if(dp[i][j][k] != -1) {

                    for(p = 0; p < n; p++) if(!(i & (1<<p))) {

                        for (q = 0; q < 6; q++) if(a[j][k] == a[p][f[q]]) {

                            t = i|(1<<p);

                            max(dp[t][p][q], dp[i][j][k] + b[p][q]);

                        }//ifq

                    }//ifp

                }//ifk

             }//fj

         }//fi

         ans = 0;

         for (i = 0; i < n; i++)

            for (j = 0; j < 6; j++) max(ans, dp[kn-1][i][j]);

         printf("%d\n", ans);

    }

    return 0;

}

posted on 2010-08-09 22:05 小志 阅读(318) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿

随笔档案(8)

文章档案(1)

相册

收藏夹

ACM --- Online Judge

小志

最新随笔

积分与排名

最新随笔

最新评论

阅读排行榜

评论排行榜