洛谷P1990 覆盖墙壁

P1990 覆盖墙壁

题目描述

你有一个长为 $N$ 宽为 $2$ 的墙壁，给你两种砖头：一个长 $2$ 宽 $1$，另一个是 L 型覆盖 $3$ 个单元的砖头。如下图：

0  0
0  00

砖头可以旋转，两种砖头可以无限制提供。你的任务是计算用这两种来覆盖 $N\times 2$ 的墙壁的覆盖方法。例如一个 $2\times 3$ 的墙可以有 $5$ 种覆盖方法，如下：

012 002 011 001 011  
012 112 022 011 001

注意可以使用两种砖头混合起来覆盖，如 $2\times 4$ 的墙可以这样覆盖：

0112
0012

给定 $N$，要求计算 $2\times N$ 的墙壁的覆盖方法。由于结果很大，所以只要求输出最后 $4$ 位。例如 $2\times 13$ 的覆盖方法为 $13465$，只需输出 $3465$ 即可。如果答案少于 $4$ 位，就直接输出就可以，不用加前导 $0$，如 $N=3$ 时输出 $5$。

输入格式

一个整数 $N$，表示墙壁的长。

输出格式

输出覆盖方法的最后 $4$ 位，如果不足 $4$ 位就输出整个答案。

输入输出样例 #1

输入 #1

13

输出 #1

3465

说明/提示

数据保证，$1\le N\le 1000000$。

这个题目，要搞懂有点难度。特别是g[n]的设定，我把我理解的两种情况，都写出来了，并且都调试成功了。

代码一：

#include<cstdio>
using namespace std;
int n;
int f[1000010],g[1000010];
const int mod=10000;
int main()
{
	scanf("%d",&n);
	f[0]=1,f[1]=1,f[2]=2,f[3]=5;
	g[0]=0,g[1]=1,g[2]=2,g[3]=4;
	//int mod=10000;
	for(int i=4;i<=n+10;++i)
	{
		f[i]=((f[i-1]+f[i-2])%mod+2*g[i-2]%mod)%mod;
		g[i]=(f[i-1]+g[i-1])%mod;
		//g[i-2]=(f[i-3]+g[i-3])%mod;
	 } 
	 printf("%d\n",f[n]);
	 return 0;
 } 

这段代码中有一个注释，是最初推导式，但用在循环里，会发现错误结果。原因是g[i]的更新滞后，导致用0代入。

代码二：

#include<cstdio>
using namespace std;
int n;
int f[1000010],g[1000010];
const int mod=10000;
int main()
{
	scanf("%d",&n);
	f[0]=1,f[1]=1,f[2]=2,f[3]=5;
	g[0]=0,g[1]=0,g[2]=1,g[3]=2;
	//int mod=10000;
	for(int i=4;i<=n+10;++i)
	{
		f[i]=((f[i-1]+f[i-2])%mod+2*g[i-1]%mod)%mod;
		//g[i]=(f[i-1]+g[i-1])%mod;
		g[i]=(f[i-2]+g[i-1])%mod;
	 } 
	 printf("%d\n",f[n]);
	 return 0;
 } 

这种情况，g[n]的理解上和上面不现，差一列，但只需要把对应的g[0]g[1]的初值搞正确，就不影响结果。