poj2663

poj2411的弱化版http://www.cnblogs.com/yzcstc/archive/2013/03/23/2977689.html
 1 /*
 2   State:Accepted
 3   Time:2013-03-19 20:41:08
 4 */
 5 #include <iostream>
 6 #include <cstring>
 7 #include <string>
 8 #include <cstdlib>
 9 #include <cstdio>
10 #include <algorithm>
11 #include <cmath>
12 using namespace std;
13 const int m = 3;
14 const int maxn = 30;
15 int f[32][30] ,data , n;
16 
17 void updata(int i , int opt , int pos){
18      if (pos == m){
19          f[i][opt] += data;   
20          return; 
21      }
22      updata(i, opt , pos + 1);
23      if ((opt & (1 << pos-1)) == 0 && (opt & (1 << pos)) == 0)
24            updata(i, opt | (1 << pos -1) | (1 << pos), pos + 1);
25      
26 }
27 
28 void dp(){
29      data = 1;
30      updata(1 , 0 , 1);
31      for (int i = 1; i < maxn; ++i)
32          for (int opt = 0; opt < (1 << m); ++opt)
33             if (f[i][opt] ){
34                  data = f[i][opt];
35                  updata(i + 1,  ~ opt &  7, 1 ); 
36             }
37    /*  for (int i = 1; i <= 2; ++i)
38         for (int  opt =0; opt < 8; ++opt)
39            printf("f[%d][%d] = %d\n",i ,opt , f[i][opt]);*/
40 }
41 
42 int main(){
43      freopen("poj2663.in","r",stdin);
44      freopen("poj2663.out","w",stdout);
45      dp();
46      while (~scanf("%d",&n) && n != -1){
47           if (n == 0) printf("1\n");
48           else printf("%d\n",f[n][7]);
49      }
50      fclose(stdin); fclose(stdout);
51 }