>Link
>解题思路
设这四个塔为 A , B , C , D A,B,C,D A,B,C,D
先考虑只有三个塔的情况，设
d
i
d_i
di为三个塔时从
A
A
A搬移
i
i
i个盘到
C
C
C的最小步数
最小步数，我们可以先把
i
−
1
i-1
i−1个盘搬到
B
B
B（三个塔，代价为
d
i
−
1
d_{i-1}
di−1），再把第
i
i
i个盘搬到
C
C
C（代价为1），最后把
i
−
1
i-1
i−1个盘从
B
B
B搬到
C
C
C
所以
d
i
=
2
∗
d
i
−
1
+
1
d_i=2* d_{i-1}+1
di=2∗di−1+1
四个塔的情况时，设
f
i
f_i
fi为四个塔时从
A
A
A搬移
i
i
i个盘到
D
D
D的最小步数，
枚举先搬的盘子数
j
(
0
<
j
<
i
)
j(0<j<i)
j(0<j<i)，先把
j
j
j个盘搬到
C
C
C（四个塔，代价为
f
j
f_j
fj），再把剩下的
i
−
j
i-j
i−j个搬到
D
D
D（
C
C
C塔已经被小的盘占用了，所以只有三个塔可以用，代价为
d
i
−
j
d_{i-j}
di−j），最后把
j
j
j个盘从
C
C
C搬到
D
D
D
所以
f
i
=
m
i
n
(
2
∗
f
j
+
d
i
−
j
)
f_i=min(2*f_{j}+d_{i-j})
fi=min(2∗fj+di−j)
>代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, d[20], f[20];
int main()
{
memset (f, 0x7f, sizeof (f));
for (int i = 1; i <= 12; i++)
d[i] = 2 * d[i - 1] + 1;
f[1] = 1;
for (int i = 2; i <= 12; i++)
for (int j = 1; j < i; j++)
f[i] = min (f[i], 2 * f[j] + d[i - j]);
for (int i = 1; i <= 12; i++)
printf ("%d\n", f[i]);
return 0;
}
因篇幅问题不能全部显示，请点此查看更多更全内容