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]); 
    } 
 
} 

作者：woshi250hua