状态压缩。分最后一个槽的值以及当前的配置方案是否可以进行DP。

1 /* 1438 */ 2 #include 
     
       3 #include 
      
        4 #include 
       
         5  6 #define MAXN 32 7  8 const int MAXS = 1<<4; 9 10 __int64 dp[MAXN][MAXS][4][2];11 int cnt[1<<4];12 13 int abs(int x) {14     return x<0 ? -x:x;15 }16 17 int main() {18     int i, j, k, n;19     int s;20     __int64 ans;21     22     memset(cnt, 0, sizeof(cnt));23     for (i=0; i
        
         = 3)52                 ans += dp[n][i][0][1] + dp[n][i][1][1] +\53                      dp[n][i][2][1] + dp[n][i][3][1];54         }55         printf("N=%d: %I64d\n", n, ans);56     }57     58     return 0;59 }