A21030.覆盖墙壁 题解

P1990 覆盖墙壁

#include<iostream>
using namespace std;
const int mod = 10000;
const int MAXN = 1e6 + 10;
int n;
int f[MAXN],g[MAXN];
int main()
{
    cin >> n;
    f[0] = 0,f[1] = 1,f[2] = 2,g[0] = 0,g[1] = 1,g[2] = 2;
    for(int i = 3;i <= n;i++)
    {
        f[i] = (f[i - 1] + f[i - 2] + 2 * g[i - 2]) % mod;
        g[i] = (f[i - 1] + g[i - 1]) % mod;
    }
    cout << f[n];
    return 0;
}