- 数学家之梦
- 2014-07-01 20:30:11 @
据说应该用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 条评论
-
308454 LV 10 @ 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