返回题解分享
讨论 / 题解分享/ 帖子详情

积木画(编程题) - 题解

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

const int N = 1e9 + 7;
int n;
int dp[2][3];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;

    dp[1][0] = 1;
    dp[1][1] = 2;
    dp[1][2] = 1;

    for(int i = 2; i <= n; i ++ ) {
        dp[i & 1][0] = (dp[(i - 1) & 1][0] + dp[(i - 1) & 1][2]) % N;
        
        dp[i & 1][1] = (dp[(i - 1) & 1][0] * 2 + dp[(i - 1) & 1][1]) % N;

        dp[i & 1][2] = (dp[(i - 1) & 1][0] + dp[(i - 1) & 1][1]) % N;
    }
    cout << dp[n & 1][0];
}
0 回复 0 转发 1 喜欢 1 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!