AcWing - 96 - 奇怪的汉诺塔 = dp

2021-02-03 12:16

阅读：717

标签：include c++ 表示 wing problem ace main 最小 content

https://www.acwing.com/problem/content/98/

先考虑三个柱子的汉诺塔问题，设d[i]表示在三个柱子都可以选时，把i个塔从一个柱子移动到另一个柱子的最小移动步数。首先把n-1个塔从A移动到B，然后把n从A移动到C，再把n-1个塔从B移动到C。

d[i]=2*d[i-1]+1

当有四个柱子时，情况稍微改变，设f[i]表示在四个柱子都可以选时，把i个塔从一个柱子移动到另一个柱子的最小移动步数，但是观察到实际上最底层的n-j个塔都是要从A到D的，而其中B和C之一必然要把顶层的塔全部放上才空出另一个塔给n-j中转（当然如果只有n一个的话是不需要中转的）。

所以先把j个塔在四个柱子的情况从A移动到B，然后ACD三个塔把n-j从A移动到D，再把j个塔在四个柱子的情况从B移动到D。

f[i]=min(f[i],2*f[j]+d[n-j])

貌似可以推广到更多柱子。

#include 
using namespace std;
typedef long long ll;

int d[13], f[13];

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    d[1] = 1;
    for(int i = 2; i

AcWing - 96 - 奇怪的汉诺塔 = dp

标签：include c++ 表示 wing problem ace main 最小 content

原文地址：https://www.cnblogs.com/Inko/p/11515577.html

上一篇：修改windows网络参数,让上网更快

下一篇：win32创建工具栏的自定义图标

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing - 96 - 奇怪的汉诺塔 = dp
文章链接：http://soscw.com/index.php/essay/50418.html

亲，登录后才可以留言！

AcWing - 96 - 奇怪的汉诺塔 = dp

评论

热门文章

推荐文章

最新文章

置顶文章