[蓝桥杯 2022 省 B] 积木画

题目描述

小明最近迷上了积木画，有这么两种类型的积木，分别为 $I$ 型（大小为 $2$ 个单位面积) 和 $L$ 型 (大小为 $3$ 个单位面积):

同时，小明有一块面积大小为 $2\times N$ 的画布，画布由 $2\times N$ 个 $1\times 1$ 区域构成。小明需要用以上两种积木将画布拼满，他想知道总共有多少种不同的方式? 积木可以任意旋转，且画布的方向固定。

输入格式

输入一个整数 $N$，表示画布大小。

输出格式

输出一个整数表示答案。由于答案可能很大，所以输出其对 $1000000007$（即 $10^9+7$）取模后的值。

样例 #1

样例输入 #1

3

样例输出 #1

5

提示

【样例说明】

五种情况如下图所示, 颜色只是为了标识不同的积木:

【评测用例规模与约定】

对于所有测试用例，$1\le N\le 10^7$。

蓝桥杯 2022 省赛 B 组 G 题。

思路

dp题目:
dp[i][0] 代表当前填满方块的方案数
dp[i][1] 代表当前只有上面一个方块的方案数
dp[i][2] 代表当前只有下面一个方块的方案数
那么状态转移方程为：
dp[i][0] = dp[i-1][0] + dp[i-2][0] + dp[i-1][1] + dp[i-1][2]
dp[i][1] = dp[i-1][2] + dp[i-2][0];
dp[i][2] = dp[i-1][1] + dp[i-1][0];

代码实现

#include<bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
int n, f[10000005][3];

int main(){
    cin >> n;
    if(n == 1){
        cout << 1 << endl;
        return 0;
    }
    f[0][0] = 1;
    f[1][0] = 1;
    for(int i = 2; i <= n; i++){
        f[i][0] = ((f[i-1][0] + f[i-2][0]) % mod + (f[i-1][1] + f[i-1][2]) % mod) % mod;
        f[i][1] = (f[i-1][2] + f[i-2][0]) % mod;
        f[i][2] = (f[i-1][1] + f[i-2][0]) % mod;
    } 
    cout << f[n][0] << endl;
    return 0;
}