本文共 835 字，大约阅读时间需要 2 分钟。

平铺方案

题目链接：

题目描述

解题思路

首先，设 $f(i)$ 表示 $i$ 格的平铺方案。

它有两种地砖，那意味着它可以放两格的砖或一格的砖来得到贡献。

而两个占一格的砖可以合成为一格两格的砖，则 $f(i-2)$ 有三种情况可以贡献到 $f(i)$。

再考虑竖着放一个一格的砖的情况，则贡献来自 $f(i-1)$。

但是，这样是不行的。我们发现在我们竖着放一格砖的时候，假如当前情况的前一个砖也是竖着的一格砖，那么就和两个一格砖合成一个两格砖的情况重复了。所以我们将两竖砖合成一两格砖的情况归入竖着放一格砖的情况。

则递推式为：
$$f(i)=2\ast f(i-2)+f(i-1)$$
记得要用高精度。

code

#include<iostream>#include<cstdio>using namespace std;int n;int f[300][100];int h[300];void e(){   	f[1][1]=1,f[2][1]=3;	h[1]=1,h[2]=1;	for(int i=3;i<=260;i++)	{   		int t=0;		for(int j=1;j<=h[i-1]+1;j++)		{   			t=f[i-2][j]*2+f[i-1][j]+t;			f[i][j]=t%10;			t/=10;		}		h[i]=h[i-1];		if(f[i][h[i-1]+1]>0)			h[i]++;	}}int main(){   	e();	while(cin>>n)	{   		for(int i=h[n];i>=1;i--)			cout<<f[n][i];		cout<<endl;	}}