poj 2663 Tri Tiling--状压dp

原题链接：​​http://poj.org/problem?id=2663​​

题意：一个3*n的表格，用一个1*2的方块填充，在填满的情况下，一共多少种填充方式。

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<string>
#include<stdio.h>
#define INF 99999999
#define eps 0.0001
using namespace std;
 
long long a[35];

int main()
{
  int n;
  a[0] = 1;
  a[2] = 3;
  for (int i = 4; i <= 30; i = i + 2)
    a[i] = a[i - 2] * 4 - a[i - 4];

  while (scanf("%d", &n) && (n != -1))
  {
    printf("%lld\n", a[n]);
  }
  return 0;
}