网站怎么做小程序,php装修公司网站源码,网站备案大概多久,apache 搭建多个网站描述
一张普通的国际象棋棋盘#xff0c;它被分成 8 乘 8 (8 行 8 列) 的 64 个方格。设有形状一样的多米诺牌#xff0c;每张牌恰好覆盖棋盘上相邻的两个方格#xff0c;即一张多米诺牌是一张 1 行 2 列或者 2 行 1 列的牌。那么#xff0c;是否能够把 32 张多米诺牌摆放…描述
一张普通的国际象棋棋盘它被分成 8 乘 8 (8 行 8 列) 的 64 个方格。设有形状一样的多米诺牌每张牌恰好覆盖棋盘上相邻的两个方格即一张多米诺牌是一张 1 行 2 列或者 2 行 1 列的牌。那么是否能够把 32 张多米诺牌摆放到棋盘上使得任何两张多米诺牌均不重叠每张多米诺牌覆盖两个方格并且棋盘上所有的方格都被覆盖住我们把这样一种排列称为棋盘被多米诺牌完美覆盖。这是一个简单的排列问题同学们能够很快构造出许多不同的完美覆盖。但是计算不同的完美覆盖的总数就不是一件容易的事情了。不过同学们 发挥自己的聪明才智还是有可能做到的。 现在我们通过计算机编程对 3 乘 n 棋盘的不同的完美覆盖的总数进行计算。 任务 对 3 乘 n 棋盘的不同的完美覆盖的总数进行计算。
输入
一次输入可能包含多行每一行分别给出不同的 n 值 ( 即 3 乘 n 棋盘的列数 )。当输入 -1 的时候结束。 n 的值最大不超过 30.
输出
针对每一行的 n 值输出 3 乘 n 棋盘的不同的完美覆盖的总数。
样例输入
2
8
12
-1样例输出
3
153
2131
解题分析
首先由于多米诺牌本身占两个格子所以如果完全覆盖的话那么n一个要偶数否则3乘上一个奇数会导致格子总数为奇数这就矛盾了。
然后我们可以明显地感知到我们当前排列的结果与前面的排列是有一定关系的。我们先计算一个n2的时候这是最小的单元n1的时候很明显不可能被完全覆盖或者从n必须为偶数理解。我们自己脑子里摆一摆知道n2的时候有三种摆法。现在我们设置一个数组dpdp[i]表示ni时的摆法。显然dp[i]中有一部分摆法是3*dp[i-2]。但是这显然没有包括全部的情况。那我们还漏掉了哪些情况
简单举个例子有两种很重要的情况被我们忽略了。比如n4的时候如果我们只是计算3*dp[2]那实际上我们在n23这两列可以横着放多米诺牌。这部分被我们忽略了。所以我们还需要考虑dp[i-4]即我们空出四列出来然后计算dp[i-4]*2然后保持这两列横着放继续i-2因为我们刚刚使用了dp[i-4]这是没有考虑i-4和i-5列横着放并且i-3和i-2列横着放的情况。
代码实现
#include iostream
using namespace std;
int dp[31]{0};int compute(int m){if(dp[m]) return dp[m];for(int i4;i30;i){dp[i]dp[i-2]*3;for(int ji-4;j0;j-2){dp[i]dp[j]*2;}}return dp[m];
}int main(){int n;dp[0]1;dp[2]3;while(cinn){if(n-1){break; }coutcompute(n)endl;}return 0;
}
