关于这题的DP方程

据说应该用dp找规律
然后蒟蒻列了一个dp方程
用f[i,j]表示i个柱j个盘的移动步数,则
f[2,0]=0 f[2,1]=1 f[2,i]=inf
f[i,j]=min(f[i,k]*2+f[i-1,j-k])
但这个方程是错误的,找出来的规律与组合数c有关,而题解里写的是与n,m线性相关的
蒟蒻翻了下vijos的题解,不是很明白规律和正确的dp方程
然而题解和其他讨论又包含很多疑点
所以
蒟蒻想请教一下各位大神和管理员
正确的dp方程是怎样的,题解里的哪种说法是正确的,感谢

4 条评论

  • @ 2014-07-11 09:42:42

    顶,求各位大神帮帮忙吧...

  • @ 2014-07-01 20:49:30

    奇怪。。蒟蒻找的规律也和组合数c有关哦,好像是个连乘再连除
    ......
    蒟蒻同求指导

  • @ 2014-07-01 20:38:15

    蒟蒻找到的规律
    n个盘的汉诺塔,又连续
    Π(n+i)/(n-3)!(0<=i<=n-4)个2^(n-1)

    请教正确的解法和规律...

  • @ 2014-07-01 20:36:13

    x盘数 2 3 3差值 4 4差值 5 5差值 6 6差值 7 7差值
    0 0 0 0 0 0 0 0 0 0 0 0
    1 1 1 1 1 1 1 1 1 1 1 1
    2 ∞ 3 2 3 2 3 2 3 2 3 2
    3 ∞ 7 4 5 2 5 2 5 2 5 2
    4 ∞ 15 8 9 4 7 2 7 2 7 2
    5 ∞ 31 16 13 4 11 4 9 2 9 2
    6 ∞ 63 32 17 4 15 4 13 4 11 2
    7 ∞ 127 64 25 8 19 4 17 4 15 4
    8 ∞ 255 128 33 8 23 4 21 4 19 4
    9 ∞ 511 256 41 8 27 4 25 4 23 4
    10 ∞ 1023 512 49 8 31 4 29 4 27 4
    11 ∞ 2047 1024 65 16 39 8 33 4 31 4
    12 ∞ 4095 2048 81 16 47 8 37 4 35 4
    13 ∞ 8191 4096 97 16 55 8 41 4 39 4
    14 ∞ 16383 8192 113 16 63 8 45 4 43 4
    15 ∞ 32767 16384 129 16 71 8 49 4 47 4
    16 ∞ 65535 32768 161 32 79 8 57 8 51 4
    17 ∞ 131071 65536 193 32 87 8 65 8 55 4
    18 ∞ 262143 131072 225 32 95 8 73 8 59 4
    19 ∞ 524287 262144 257 32 103 8 81 8 63 4
    20 ∞ 1048575 524288 289 32 111 8 89 8 67 4
    21 ∞ 2097151 1048576 321 32 127 16 97 8 71 4
    22 ∞ 4194303 2097152 385 64 143 16 105 8 79 8
    23 ∞ 8388607 4194304 449 64 159 16 113 8 87 8
    24 ∞ 16777215 8388608 513 64 175 16 121 8 95 8
    25 ∞ 33554431 16777216 577 64 191 16 129 8 103 8
    26 ∞ 67108863 33554432 641 64 207 16 137 8 111 8
    27 ∞ 134217727 67108864 705 64 223 16 145 8 119 8
    28 ∞ 268435455 134217728 769 64 239 16 153 8 127 8
    29 ∞ 536870911 268435456 897 128 255 16 161 8 135 8
    30 ∞ 1073741823 536870912 1025 128 271 16 169 8 143 8
    31 ∞ 2147483647 1073741824 1153 128 287 16 177 8 151 8
    32 ∞ 4294967295 2147483648 1281 128 303 16 185 8 159 8
    33 ∞ 8589934591 4294967296 1409 128 319 16 193 8 167 8
    34 ∞ 17179869183 8589934592 1537 128 335 16 201 8 175 8
    35 ∞ 34359738367 17179869184 1665 128 351 16 209 8 183 8
    36 ∞ 68719476735 34359738368 1793 128 383 32 225 16 191 8
    37 ∞ 1.37439E+11 68719476736 2049 256 415 32 241 16 199 8
    38 ∞ 2.74878E+11 1.37439E+11 2305 256 447 32 257 16 207 8
    39 ∞ 5.49756E+11 2.74878E+11 2561 256 479 32 273 16 215 8
    40 ∞ 1.09951E+12 5.49756E+11 2817 256 511 32 289 16 223 8
    41 ∞ 2.19902E+12 1.09951E+12 3073 256 543 32 305 16 231 8
    42 ∞ 4.39805E+12 2.19902E+12 3329 256 575 32 321 16 239 8
    43 ∞ 8.79609E+12 4.39805E+12 3585 256 607 32 337 16 247 8
    44 ∞ 1.75922E+13 8.79609E+12 3841 256 639 32 353 16 255 8
    45 ∞ 3.51844E+13 1.75922E+13 4097 256 671 32 369 16 263 8
    46 ∞ 7.03687E+13 3.51844E+13 4609 512 703 32 385 16 271 8
    47 ∞ 1.40737E+14 7.03687E+13 5121 512 735 32 401 16 279 8
    48 ∞ 2.81475E+14 1.40737E+14 5633 512 767 32 417 16 287 8
    49 ∞ 5.6295E+14 2.81475E+14 6145 512 799 32 433 16 295 8
    50 ∞ 1.1259E+15 5.6295E+14 6657 512 831 32 449 16 303 8
    51 ∞ 2.2518E+15 1.1259E+15 7169 512 863 32 465 16 311 8
    52 ∞ 4.5036E+15 2.2518E+15 7681 512 895 32 481 16 319 8
    53 ∞ 9.0072E+15 4.5036E+15 8193 512 927 32 497 16 327 8
    54 ∞ 1.80144E+16 9.0072E+15 8705 512 959 32 513 16 335 8
    55 ∞ 3.60288E+16 1.80144E+16 9217 512 991 32 529 16 343 8
    56 ∞ 7.20576E+16 3.60288E+16 10241 1024 1023 32 545 16 351 8
    57 ∞ 1.44115E+17 7.20576E+16 11265 1024 1087 64 561 16 367 16
    58 ∞ 2.8823E+17 1.44115E+17 12289 1024 1151 64 577 16 383 16
    59 ∞ 5.76461E+17 2.8823E+17 13313 1024 1215 64 593 16 399 16
    60 ∞ 1.15292E+18 5.76461E+17 14337 1024 1279 64 609 16 415 16

  • 1

信息

ID
1432
难度
7
分类
组合数学 点击显示
标签
递交数
348
已通过
58
通过率
17%
被复制
4
上传者