首页 > ACM题库 > HDU-杭电 > HDU 1438 钥匙计数之一-动态规划-[解题报告] C++
2013
12-10

HDU 1438 钥匙计数之一-动态规划-[解题报告] C++

钥匙计数之一

问题描述 :

一把锁匙有N个槽,槽深为1,2,3,4。每锁匙至少有3个不同的深度且至少有1对相连的槽其深度之差为3。求这样的锁匙的总数。

输入:

本题无输入

输出:

对N>=2且N<=31,输出满足要求的锁匙的总数。

样例输出:

N=2: 0
N=3: 8
N=4: 64
N=5: 360
..
..
..
..
..
..
..

N=31: ...

注:根据Pku Judge Online 1351 Number of Locks或 Xi'an 2002 改编,在那里N<=16

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1438

题目大意一把锁匙有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

代码:

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

}


本文ZeroClock原创,但可以转载,因为我们是兄弟。

解题报告转自:http://blog.csdn.net/woshi250hua/article/details/7743926