积木画 参考代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int MOD = 1000000007;
const int maxn = 10000000 + 100;
int n;
int dp[maxn][3];

int add(int a, int b) {
    a += b;
    if (a >= MOD) {
        return a - MOD;
    }
    return a;
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif  // ExRoc
    ios::sync_with_stdio(false);

    cin >> n;
    dp[1][0] = 1;
    dp[2][0] = 2;
    dp[2][1] = 1;
    dp[2][2] = 1;
    for (int i = 3; i <= n; ++i) {
        dp[i][0] = add(add(dp[i - 1][0], dp[i - 2][0]), add(dp[i - 1][1], dp[i - 1][2]));
        dp[i][1] = add(dp[i - 1][2], dp[i - 2][0]);
        dp[i][2] = add(dp[i - 1][1], dp[i - 2][0]);
    }
    cout << dp[n][0] << endl;

    return 0;
}