Hdu 1438 鑰匙計數之一 (DP_狀態壓縮DP）

題目大意：一把鎖匙有N個槽，槽深為1，2，3，4。每鎖匙至少有3個不同的深度且至少有1對相連的槽其深度之差為3。求這樣的鎖匙的總數。

解題思路：手賤用狀態DP來寫這遞推題，用狀態DP很好想但是編程略微復雜。用dp[i][j][k][s]來表示排到鑰匙的第i個糟，i以前的槽深總狀態為j，以槽深k結尾，s為0、1,0表示這之前沒有深度之差為3的槽，1表示有深度之差為3的槽。然後枚舉各種狀態各種槽深，1->1，如果前後槽深之差為3則0->1,否則0->0.

數據輸出：
N=2: 0
N=3: 8
N=4: 64
N=5: 360
N=6: 1776
N=7: 8216
N=8: 36640
N=9: 159624
N=10: 684240
N=11: 2898296
N=12: 12164608
N=13: 50687208
N=14: 209961648
N=15: 865509848
N=16: 3553389280
N=17: 14538802248
N=18: 59313382032
N=19: 241378013240
N=20: 980200805824
N=21: 3973116354984
N=22: 16078778126448
N=23: 64978668500120
N=24: 262277950619296
N=25: 1057528710767880
N=26: 4260092054072400
N=27: 17147133531655928
N=28: 68968784226289024
N=29: 277229417298013800
N=30: 1113741009496217136
N=31: 4472142617535586136

代碼：
[cpp] 
#include <stdio.h> 
#include <string.h> 
 
 
__int64 dp[40][40][40][3]; 
__int64 one[40], num[40]; 
 
int abs(int x) { 
 
    return x > 0 ? x : -x; 
} 
 
int main() { 
    int i, j, k, s, cur, pre; 
    int ii, jj, kk, ss,n; 
 
 
    for (i = 0; i <= 15; ++i) 
        for (j = 0; j < 4; ++j) 
            if (i & (1 << j)) one[i]++; 
    memset(dp,0,sizeof(dp)); 
    for (i = 0; i < 4; ++i) 
        dp[1][1 << i][i][0] = 1; 
 
 
    for (i = 2; i <= 31; ++i)  
        for (j = 0; j <= 15; ++j) 
            for (k = 0; k < 4; ++k)  
                for (s = 0; s < 4; ++s) { 
  
                    cur = (j | (1 << s)); 
                    dp[i][cur][s][1] += dp[i - 1][j][k][1]; 
                    if (abs(k - s) == 3) 
                        dp[i][cur][s][1] += dp[i - 1][j][k][0]; 
                    else dp[i][cur][s][0] += dp[i - 1][j][k][0]; 
                } 
 
     
    for (i = 2; i <= 31; ++i) { 
 
        for (j = 0; j <= 15; ++j) 
            if (one[j] >= 3) for (k = 0; k < 4; ++k) 
                    num[i] += dp[i][j][k][1]; 
        printf("N=%d: %I64d\n", i, num[i]); 
    } 
 
}