AJJak-T004: Tiling-3.5

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

typedef long long lli;

const int N = 1000 + 5;

lli dp1[N], dp2[N], dp3[N];

int main(){

    int n;
    scanf("%d", &n);
    int lst = 5;
    dp1[0] = 1; dp1[1] = 1;
    dp2[0] = 1; dp2[1] = 2;
    dp3[0] = 1; dp3[1] = 1;
    for(int i = 2; i <= n; ++i){
        dp1[i] = dp1[i - 1] + dp1[i - 2] + 2 * dp2[i - 2] + dp3[i - 2];
        dp2[i] = dp1[i] + dp2[i - 1];
        dp3[i] = dp1[i] + dp3[i - 2];

    }
    cout << dp1[n];

    return 0;
}