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 3 2 8 12 ?

Sample Output 3 171 2731 ?

很好的一道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;
}

轉載于:https://www.cnblogs.com/smilesundream/p/6642579.html

總結

以上是生活随笔為你收集整理的hdu 2510的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。