2530 Tiling a Grid With Dominoes

domino.cpp

//http://www.spoj.com/problems/GNY07H/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>

#define MAXN 100000

using namespace std;

int memo[MAXN];

int f(int n) {
    if(memo[n] != -1) return memo[n];
    if(n == 0 || n == 1) return memo[n] = 1;
    if(n == 2) return memo[n] = 5;
    if(n == 3) return memo[n] = 11;
    return memo[n] = f(n-1) + 5*f(n-2) + f(n-3) - f(n-4);
}

int main() {
    int dp[MAXN];
    memset(memo,(-1),sizeof(memo));
    dp[0] = dp[1] = 1; dp[2] = 5; dp[3] = 11;
    for(int i = 4; i < MAXN; i++)
        dp[i] = dp[i-1] + 5*dp[i-2] + dp[i-3] - dp[i-4];

    int n,w;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &w);
        printf("%d %d\n", i, dp[w]);
        //printf("%d %d\n", i, f(w));
    }

    return 0;
}