平铺方案

题目描述

解题思路

设f(i)表示2*i矩阵的方案数

第i列上竖着放一个2 * 1的，方案数为f(i-1)
第i列与第i-1列放一个2 * 2的，方案数为f(i-2)
第i列与第i-1列横着放一个1 * 2的，方案数为f(i-2)

故递推式为
f [ i ] = f [ i − 2 ] ∗ 2 + f [ i − 1 ] f[i]=f[i-2]*2+f[i-1] f[i]=f[i−2]∗2+f[i−1]
初值：f[0]=f[1]=1 f[2]=3

因为本题n最大为250，会炸long long
所以要用高精度

AC代码

#include<cstdio>
using namespace std;
int n,f[255][205];
int main()
{
   
	f[0][200]=f[1][200]=1;//初值
	f[2][200]=3;
	for(int i=3;i<=250;i++)//预处理，递推
 	{
   
 		int o=0;
 		for(int j=200;j>=1;j--)//高精乘
		{
   
			f[i][j]=f[i-2][j]*2+o;
			o=f[i][j]/10;
			f[i][j]%=10;
		}
		o=0;
		for(int j=200;j>=1;j--)//高精加
		{
   
			f[i][j]+=f[i-1][j]+o;
			o=f[i][j]/10;
			f[i][j]%=10;
		}
	}
	while(scanf("%d",&n)!=EOF)
	{
   
		int j=1;//去0
		while(f[n][j]==0)j++;
		for(int i=j;i<=200;i++)
	 	 printf("%d",f[n][i]);
	 	printf("\n"); 
	}
	return 0;
}

谢谢