?????目录

题目?

题解

题目?

对于一个?2?行?N?列的走道。现在用?1×2,2×2?的砖去铺满。问有多少种不同的方式。

下图是一个?2?行?17?列的走道的某种铺法。

输入格式

一个数字?N，0≤n≤250。

输出格式

方案数。（对 100007?取模）。

输出时每行末尾的多余空格，不影响答案正确性

要求使用「文件输入输出」的方式解题，输入文件为?wall.in，输出文件为?wall.out

样例输入1

2

样例输出1

3

样例输入2

8

样例输出2

171

题解：

知识点：动态规划

分析：设dp[i]表示2行i列的铺砖方案数，考虑第i列，它可以由1个1*2竖放铺成，方案数量即dp[i-1]，也可由1个2*2覆盖，方案数量即dp[i-2]，也可由2个1*2横放覆盖，方案数量即dp[i-2]，所以可得状态转移方程dp[i]=dp[i-1]+2*dp[i-2];，其中，dp[1]=1，dp[2]=3。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int N=255,mod=100007;
int dp[N];
int main(){
    freopen("wall.in","r",stdin);
    freopen("wall.out","w",stdout);
    dp[1]=1;//注意初始化
    dp[2]=3;
    for (int i=3;i<=N;i++){//注意从3开始
        dp[i]=(dp[i-1]%mod+2*dp[i-2]%mod)%mod;//注意取余方式
    }
    int n;
    cin>>n;
    cout<<dp[n]<<endl;
    return 0;
}