Tiling_easy version

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 585 Accepted Submission(s): 511

Problem Description

有一个大小是 2 x n 的网格，现在需要用2种规格的骨牌铺满，骨牌规格分别是 2 x 1 和 2 x 2，请计算一共有多少种铺设的方法。

Input

输入的第一行包含一个正整数T（T<=20），表示一共有 T组数据，接着是T行数据，每行包含一个正整数N（N<=30），表示网格的大小是2行N列。

Output

输出一共有多少种铺设的方法，每组数据的输出占一行。

Sample Input

Sample Output

31712731

很好的一道dp题目，递推很重要，假设目前有n列，则在第n列，可以放一块2*1,即竖着放，则dp[n]与dp[n-1]相同

也可以让其与前面的第n-1列一起放一个2*2大的，或者一起放两块1*2即横着放，所以dp[n]=dp[n-1]+2*dp[n-2];,,果然好题，不过dp数组也可以不用long long 刚刚查了下，int 最大可以表示20亿多一点，也就是十位数，在32位的情况下,而long long 最大可以表示9223372036854775807共19位数

#include<iostream>

#include<cstdio>
#include<cstring>
using namespace std;
long long dp[31];
int main()
{

dp[1]=1;dp[2]=3;
for(int i=3;i<=30;i++)
dp[i]=dp[i-1]+2*dp[i-2];
int n,cas;
cin>>cas;
while(cas--)
{

cin>>n;
cout<<dp[n]<<endl;
}
return 0;
}

转载地址：http://kcgsi.baihongyu.com/

你可能感兴趣的文章