POJ 2663

解题方法因为只有 3 所以我列举了所有状态 000 111 001 100 110 011 每一层只有 6个状态；简化了搜索的过程

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 int N,dp[33][8];
 8 int work( )
 9 {
10     memset(dp,0,sizeof(dp));
11     dp[0][2] = 1;
12     for( int i = 1; i <= N; i++ )
13     {
14         dp[i][1] = dp[i-1][2];
15         dp[i][2] = dp[i-1][1] + dp[i-1][3] + dp[i-1][4];
16         dp[i][3] = dp[i-1][2] + dp[i-1][5]  ;
17         dp[i][4] = dp[i-1][2] + dp[i-1][6];
18         dp[i][5] = dp[i-1][3];
19         dp[i][6] = dp[i-1][4];
20     }
21     return dp[N][2];
22 }
23 int main( )
24 {
25     while( scanf("%d",&N) && N >= 0 )
26     {
27         if( N*3%2 )printf("0\n");
28         else       printf("%d\n",work( ));
29     }
30     return 0;
31 }