铺地砖

时间限制: 1 Sec  内存限制: 128 MB

题目描述

一天，晨晨的数学老师布置了一道题目，大意如下：用1×1和2×2的磁砖不重叠地铺满n×3的地板，共有多少种方案？
例如：n=1时：1×3的地板方法就一个，直接由三个1×1的磁砖铺满。
      n=2时：2×3的地板可以由下面3种方案铺满：

 

输入

第一行：一个整数n（1≤n≤100）。

 

输出

输出铺满n×3的地板的方案数。

 

样例输入

复制样例数据

3

样例输出

5

 

提示

对于20%的数据，1≤n≤15；
对于50%的数据，1≤n≤30;
对于100%的数据，1≤n≤100;

 

设宽为n的时候方案数为f[n];

根据这张图可以发现，宽为2，长为3的有3种方法。由于长是固定为3的，那么当宽大于2的时候，可以试着找

通过n-1,n-2的宽度来找，去掉n-1行，那么就剩下最后一行，只能铺1*1的砖3块,所以为f[n-1]；去掉n-2行，那么还剩下两行，也就只有上面三种方法，是3种吗，看方法三，和去掉n-1行重复了，所以只有2种方法为2*f[n-2];

所以总共f[n]=f[n-1]+2*f[n-2];

由于数据太大，用大数做。

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int f[105][10005];
int n;

void solve(int a[], int b[], int c[]){
	for (int i = 1; i <= b[0]; i++){
		a[i] += 2 * b[i];
		if(a[i] > 9){
			a[i + 1] += a[i] / 10;
			a[i] %= 10;
		}
	}
	int len = b[0];
	while(a[len + 1]) len++;
	for (int i = 1; i <= c[0]; i++){
		a[i] += c[i];
		if(a[i] > 9){
			a[i + 1]++;
			a[i] -= 10;
		}
	}
	int cnt = c[0];
	while(a[cnt + 1]){
		if(a[cnt + 1] > 9){
			a[cnt + 2]++;
			a[cnt + 1] -= 10;
			cnt++;
		}else{
			cnt++;
			break;
		}
	}
	a[0] = max(cnt, len);
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &n);
	f[1][0] = 1, f[1][1] = 1, f[2][0] = 1, f[2][1] = 3;
	for (int i = 3; i <= n; i++){
		solve(f[i], f[i - 2], f[i - 1]);
	}
	for (int i = f[n][0]; i >= 1; i--) printf("%d", f[n][i]);
	printf("\n");

	return 0;
}
/**/