【POJ 2663】Tri Tiling（dp|遞推）

Tri Tiling Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 9912 Accepted: 5072 Description In how many ways can you tile a 3xn rectangle with 2x1 dominoes?  Here is a sample tiling of a 3x12 rectangle.  Input Input consists of several test cases followed by a line containing -1. Each test case is a line containing an integer 0 <= n <= 30. Output For each test case, output one integer number giving the number of possible tilings. Sample Input 2 8 12 -1 Sample Output 3 153 2131 Source Waterloo local 2005.09.24

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   

Go Back  

To top

[題意][用1×2的小矩陣填充3×n，一共有多少種方法]

【題解】【遞推】

【明明是dp,卻硬生生的寫成了遞推 】

【完整的2*3矩形有3種拼法，是以f[n]+=3*f[n-2]。 

  當突出兩塊時：突出的兩塊時上側兩個：發現往後拼隻有一種方法。突出的兩塊在下側時同樣一個，于是用這種突出的方法拼出f[n]有兩種（就是以三個一組，兩組并在一起時，将中間的兩個豎放的改為橫着的）。即f[n]+=2*(f[n-4]+f[n-6]+..+f[0]). 】

【于是f[n]=3*f[n-2]+2*(f[n-4]+..+f[0])，求通項得：f[n]=4*f[n-2]-f[n-4].】

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[40];
int main()
{
	int i,j;
	f[0]=1; f[2]=3;
	for (i=4;i<=30;i+=2)
	 f[i]=4*f[i-2]-f[i-4];
	while (scanf("%d",&j)==1&&j!=-1)
	 printf("%d\n",f[j]);
	return 0;
}