算法题目——多米诺骨牌问题(POJ-2663)

谁借莪１个温暖的怀抱￠ 2022-08-28 11:00 135阅读 0赞

题目链接：[POJ-2663][]  
设有形状一样的多米诺牌，每张牌恰好覆盖棋盘上相邻的两个方格，即一张多米诺牌是一张 1 行 2 列或者 2 行 1 列的牌。那么，是否能够把 32 张多米诺牌摆放到棋盘上，使得任何两张多米诺牌均不重叠，每张多米诺牌覆盖两个方格，并且棋盘上所有的方格都被覆盖住？我们把这样一种排列称为棋盘被多米诺牌完美覆盖。这是一个简单的排列问题，同学们能够很快构造出许多不同的完美覆盖。但是，计算不同的完美覆盖的总数就不是一件容易的事情了。不过，同学们 发挥自己的聪明才智，还是有可能做到的。  
![在这里插入图片描述][3b1bf5169aab423387dbd6614862b04b.png]  
**输入**

一次输入可能包含多行，每一行分别给出不同的 n 值 ( 即 3 乘 n 棋盘的列数 )。当输入 -1 的时候结束。  
n 的值最大不超过 30.  
**输出**

针对每一行的 n 值，输出 3 乘 n 棋盘的不同的完美覆盖的总数。

思路:  
设a\[i\]为N=i时的方法数.i为奇数的时候肯定为0.

如果i为偶数,a\[i\]可以看成a\[i-2\]加上两个单位组成的,此时多出来的2单位有3种方法…

也可以看成a\[i-4\]加上四个单位组成的,此时这四个单位一定是连在一起的,中间不能分割,所以只有两种放法.

同理,可看成a\[i-6\]加上六个单位组成的,此时这六个单位也连在一起,不能分割,只有两种放法…

直到所有的砖块都是连在一起的,中间不能分割,也只有两种放法.

所以  
a\[i\]=3*a\[i-2\]+2*(a\[i-4\]+a\[i-6\]+…+a\[0\]) ①

a\[i-2\]=3*a\[i-4\]+2*(a\[i-6\]+…a\[0\]) ②

①-②,得a\[i\]=4\*a\[i-2\]-a\[i-4\].  
参考文章  
[POJ 2663 Tri Tiling(完美覆盖)][POJ 2663 Tri Tiling]

#include <stdio.h>
    #include <stdlib.h>
    #include <iostream>
    #include<vector>
    using namespace std;
    
    int main()
    {
        
        int i,n;
        long long int a[31];
        a[0]=1;
        a[2]=3;
        for(i=4;i<=30;i+=2)
    	{
        
        	a[i]=4*a[i-2]-a[i-4];
        }
        
        
        vector<int> vec;
        while(scanf("%d",&n)&&n!=-1){
        
            if(n%2==1){
        
                vec.push_back(0);
                continue;
            }
            else
            	vec.push_back(a[n]);
                
        }
        
        for(int i=0;i<vec.size();i++)
        {
        
        	printf("%I64d\n",vec[i]);
    	}
    	
    	
        return 0;
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oiR5Lus5LiN55Sf5Lqn5Luj56CB77yM5Y-q5piv5Luj56CB55qE5pCs6L-Q5bel_size_8_color_FFFFFF_t_70_g_se_x_16]

[POJ-2663]: http://poj.org/problem?id=2663
[3b1bf5169aab423387dbd6614862b04b.png]: /images/20220828/bc9ddd8233514a9cbbaa9d4c9a87dad4.png
[POJ 2663 Tri Tiling]: https://blog.csdn.net/tp7309/article/details/53142265?ops_request_misc=&request_id=&biz_id=102&utm_term=poj2663&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-6-53142265.first_rank_v2_pc_rank_v29&spm=1018.2226.3001.4187
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oiR5Lus5LiN55Sf5Lqn5Luj56CB77yM5Y-q5piv5Luj56CB55qE5pCs6L-Q5bel_size_8_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/c0a0caf248c04b72b2cbb59ba7cb1942.png