poj2663 Tri Tiling 解题报告

题目地址：http://poj.org/problem?id=2663

递推题，推导有点复杂，可能还有更好的办法吧，下面是我的想法

用$f_n$表示铺成$3 \times n$没铺满，还有一个空缺，$g_n$表示铺成$3 \times n$没铺满，有两个空缺，用$a_n$表示铺成$3 \times n$时全部铺满。

则很容易知道如果要铺成$a_n$，只需要$g_n$再加一块或者$f_{n-1}$再加两块，故$a_n=g_n+f_{n-1}$

同理，可知只要$f_{n-1}$再加一块就是$g_n$，而$f_n$则是只需要$a_{n-1}$再加一块或者$g_{n-1}$上加（需要点空间想像），综上，就可以推出递推公式了

poj2663 Tri Tilingview raw

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
int a[35];
int f[35];
int g[35];
int main()
{
	int n;
	a[0]=1;
	int i;
	for(i=1;i<31;i++)
	{
		f[i]=2*a[i-1]+g[i-1];
		g[i]=f[i-1];
		a[i]=f[i-1]+a[i-2];
	}
	while(scanf("%d",&n),n+1)
		printf("%d\n",a[n]);
}