首页 > ACM题库 > HDU-杭电 > hdu 2077 汉诺塔IV-动态规划-[解题报告]C++
2013
12-29

hdu 2077 汉诺塔IV-动态规划-[解题报告]C++

汉诺塔IV

问题描述 :

还记得汉诺塔III吗?他的规则是这样的:不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出),也不允许大盘放到小盘的上面。xhd在想如果我们允许最大的盘子放到最上面会怎么样呢?(只允许最大的放在最上面)当然最后需要的结果是盘子从小到大排在最右边。

输入:

输入数据的第一行是一个数据T,表示有T组数据。
每组数据有一个正整数n(1 <= n <= 20),表示有n个盘子。

输出:

输入数据的第一行是一个数据T,表示有T组数据。
每组数据有一个正整数n(1 <= n <= 20),表示有n个盘子。

样例输入:

2
1
10

样例输出:

2
19684

题意:

还记得汉诺塔III吗?他的规则是这样的:不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出),也不允许大盘放到小盘的上面。xhd在想如果我们允许最大的盘子放到最上面会怎么样呢?(只允许最大的放在最上面)当然最后需要的结果是盘子从小到大排在最右边。

分析:

dp[i][0]表示将 i 个盘子从两边移动到中间的步数

dp[i][1]表示将 i 个盘子从中间移动到两边的步数

讲n个盘子从左边移动到右边的总步数为 dp[i-1][0]+dp[i-1][1]+2

#include <cstdio>
#include <cstring>
int dp[22][2];
int main()
{
    dp[0][0] = dp[0][1] = 0;
    for (int i=1; i<=20; i++){
        dp[i][0] = 2*dp[i-1][0]+dp[i-1][1]+1;
        dp[i][1] = dp[i-1][0]+2*dp[i-1][1]+1;
    }
    int t, n;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d",&n);
        printf("%d\n",dp[n-1][0]+dp[n-1][1]+2);
    }
    return 0;
}

 

解题转自:http://www.cnblogs.com/dream-wind/archive/2013/02/12/2910322.html


  1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确

  2. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c