HDOJ1143 Tri Tiling

题目链接：HDOJ1143

每天一个A+B，第34天~

3*n的矩阵之中，用1*2的骨牌将其填满，问总方案数

这个题数据量很小，n最大是30，而且给定了几个值来检验

这种题首先肯定可以确定是数学题，大的数值是由小的数值递推过来

2的时候，是哪3种呢？

其中第一种上下翻转可以得到第三种

4的时候呢，有两种情况，2+2类型的，乘法原理知有3*3=9种

另一种就是4单独构成，有2种

所以有11种

所以可以直接用数学方法先搞出来

这个题，当成排列组合去算
首先分类相加
然后在每个类中，先选定位置，然后乘法原理，除了2是3种情况，其他的数字都是2种
2    3
4    2+2    3*3=9
    4    2
    总共11种
6    2+2+2 3*3*3=27
    2+4 2*3*2=12
    6 2
    总共41种
8    2+2+2+2 3*3*3*3=81
    2+2+4 3*3*3*2=54
    4+4 2*2=4
    2+6 2*3*2=12
    8 2
    总共153种
10     2+2+2+2+2 3*3*3*3*3=243
    2+2+2+4 4*2*3*3*3=216
    2+4+4 3*3*2*2=36
    2+2+6 3*2*3*3=54
    4+6 2*2*2=8
    2+8 2*2*3=12
    10 2
    总共571种
12    2+2+2+2+2+2 3*3*3*3*3*3=729
    2+2+2+2+4 5*2*3*3*3*3=810
    2+2+4+4 6*2*2*3*3=216    C(4,2)
    4+4+4 2*2*2=8
    2+2+2+6 4*3*3*3*2=216
    2+4+6 6*3*2*2=72     A(3,3)
    6+6 2*2=4
    2+2+8 3*2*3*3=54
    4+8 2*2*2=8
    2+10 2*3*2=12
    12 2
    总共2131种
所以根据这些数据去推递推公式
虽然还是不明白为什么了

公式1：
dp[n]=4*dp[n-2]-dp[n-4]
公式2：
dp[n]=3*(dp[n-2]+dp[n-4])-dp[n-6]
其实公式1写两个，dp[n],dp[n-2]
然后叠加就得到了公式2

最后代码很简单的，有没有聚聚能告诉我是怎么推出来公式的

#include<bits/stdc++.h>
using namespace std;

const int maxn=50;
__int64 ans[maxn];

int main(){
	ans[0]=1;
	ans[2]=3;
	ans[4]=11;
	ans[6]=41;
	for(int i=8;i<=30;i++)
		ans[i]=4*ans[i-2]-ans[i-4];
	int n;
	while(scanf("%d",&n),n!=-1){
		if (n%2==0) cout<<ans[n]<<endl;
		else cout<<"0"<<endl;
	}
	return 0;
}