首页 > 代码库 > hdu1143 Tri Tiling(递推)

hdu1143 Tri Tiling(递推)

题目链接:

huangjing

首先考虑长为奇数的情况,你试着画几个就会发现那个根本不可能成立,所以只有长度为偶数的情况才可以。。

然后就会发现除了2这种特殊情况外,其余的2 4 6 8都只有两种情况

具体参看 http://blog.csdn.net/chaoojie/article/details/8860935

把 4, 6, 8.... 看成一整块,就有下图两种情况(正着,倒着)

那么递推公式就出来了

F[N]=F[2]*F[N-2]+F[4]*F[N-4]+.......F[N]*F[0]

F[N-2]=F[2]*F[N-4]+F[4]*F[N-6]+......F[N-2]*F[0]

又我们刚才得出结论除了F[2]=3,其余的都等于2

所以两个式子相减得到

F[N]=4*F[N-2]-F[N-4]

直接打表计算即可。。。

代码:

#include<cstdio>
#include<cstring>
const int maxn=31+10;

int dp[maxn],n;


int main()
{
    dp[0]=1;
    dp[2]=3;
    for(int i=4;i<=32;i++)
        dp[i]=4*dp[i-2]-dp[i-4];
    while(~scanf("%d",&n)&&n!=-1)
    {
        if(n%2)  printf("0\n");
        else printf("%d\n",dp[n]);
    }
    return 0;
}



hdu1143 Tri Tiling(递推)