HDU 2046 骨牌铺方格（递推+打表）

HDU 2046 骨牌铺方格（递推+打表）

骨牌铺方格

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 42690    Accepted Submission(s): 20697

Problem Description

在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数.

例如n=3时,为2× 3方格，骨牌的铺放方案有三种,如下图：

Input

输入数据由多行组成，每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0

Output

对于每个测试实例，请输出铺放方案的总数，每个实例的输出占一行。

Sample Input

1 3 2

Sample Output

1 3 2

Author

lcy

Source

​​递推求解专题练习（For Beginner） ​​

题解：

先考遇加一个骨牌； r[n-1]表示n-1个骨牌排列方式种数，加第n个骨牌的时候，可以在前竖着加，也可在后竖着加进去。但r[n-1]的种数里每种图形要么自身对称，要么能找到与之对应的图形，这时在前面加进去和在后面加进去的情况就会重复，所以只算其中一种。（不考遇插中间。第n个插中间，相当于把自身融入那r[n-1]种排列方式中，多出来的第n个就相当于要插入最前面的骨牌，所以插中间与插最前面是等效的）种数=r[n-1]； 再考遇加两个骨牌。 同理，横加两个，不考遇竖加的情况。因为竖加两个与r[n-1]里的种数重复，种数=r[n-2]； (加3个或奇数个骨牌与加1个骨牌是等效的，比如在r[n-3]后插3个与r[n-1)后插一个等效，前者多出来的2个可任意插，相当于r[n-3]加了两个，变成r[n-1]） （加4个或偶数个骨牌与加两个等效，同理）所以只考遇加一个或两个骨牌的情况。 总种数=r[n-2]+r[n-1];

AC代码：

#include#include#include#include#include#include#include#include#include#includetypedef long long LL;using namespace std;int main(){ long long int i,a[52],n; a[1]=1;a[2]=2; for(i=3;i<51;i++) a[i]=a[i-1]+a[i-2]; while(~scanf("%d",&n)) { printf("%lld\n",a[n]); } return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。