专栏首页算法修养POJ-1958 Strange Towers of Hanoi(线性动规)

POJ-1958 Strange Towers of Hanoi(线性动规)

Strange Towers of Hanoi Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 2677 Accepted: 1741 Description

Background Charlie Darkbrown sits in another one of those boring Computer Science lessons: At the moment the teacher just explains the standard Tower of Hanoi problem, which bores Charlie to death!

The teacher points to the blackboard (Fig. 4) and says: “So here is the problem: There are three towers: A, B and C. There are n disks. The number n is constant while working the puzzle. All disks are different in size. The disks are initially stacked on tower A increasing in size from the top to the bottom. The goal of the puzzle is to transfer all of the disks from tower A to tower C. One disk at a time can be moved from the top of a tower either to an empty tower or to a tower with a larger disk on the top.

So your task is to write a program that calculates the smallest number of disk moves necessary to move all the disks from tower A to C.” Charlie: “This is incredibly boring—everybody knows that this can be solved using a simple recursion.I deny to code something as simple as this!” The teacher sighs: “Well, Charlie, let’s think about something for you to do: For you there is a fourth tower D. Calculate the smallest number of disk moves to move all the disks from tower A to tower D using all four towers.” Charlie looks irritated: “Urgh… Well, I don’t know an optimal algorithm for four towers… ” Problem So the real problem is that problem solving does not belong to the things Charlie is good at. Actually, the only thing Charlie is really good at is “sitting next to someone who can do the job”. And now guess what — exactly! It is you who is sitting next to Charlie, and he is already glaring at you. Luckily, you know that the following algorithm works for n <= 12: At first k >= 1 disks on tower A are fixed and the remaining n-k disks are moved from tower A to tower B using the algorithm for four towers.Then the remaining k disks from tower A are moved to tower D using the algorithm for three towers. At last the n - k disks from tower B are moved to tower D again using the algorithm for four towers (and thereby not moving any of the k disks already on tower D). Do this for all k 2 ∈{1, …. , n} and find the k with the minimal number of moves. So for n = 3 and k = 2 you would first move 1 (3-2) disk from tower A to tower B using the algorithm for four towers (one move). Then you would move the remaining two disks from tower A to tower D using the algorithm for three towers (three moves). And the last step would be to move the disk from tower B to tower D using again the algorithm for four towers (another move). Thus the solution for n = 3 and k = 2 is 5 moves. To be sure that this really is the best solution for n = 3 you need to check the other possible values 1 and 3 for k. (But, by the way, 5 is optimal… ) Input

There is no input. Output

For each n (1 <= n <= 12) print a single line containing the minimum number of moves to solve the problem for four towers and n disks. Sample Input

No input. Sample Output

REFER TO OUTPUT.

线性动规,递推即可,不用记忆化搜索。

#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stdlib.h>

using namespace std;
int dp[13][2];
int hanoi(int n)
{
    if(n==1)
        return dp[n][0]=1;
    else
        return dp[n][0]=2*hanoi(n-1)+1;
}
int main()
{
    for(int i=1;i<=12;i++)
        dp[i][1]=999999;
    hanoi(12);
    dp[1][1]=1;
    for(int i=2;i<=12;i++)
    {
        for(int j=1;j<i;j++)
        {
            dp[i][1]=min(dp[i][1],2*dp[i-j][1]+dp[j][0]);
        }
    }
    for(int i=1;i<=12;i++)
        printf("%d\n",dp[i][1]);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • CodeForces 665A Buses Between Cities

    A. Buses Between Cities time limit per test 1 second memory limit per test ...

    ShenduCC
  • POJ-1953 World Cup Noise(线性动规)

    World Cup Noise Time Limit: 1000MS Memory Limit: 30000K Total Submissio...

    ShenduCC
  • ZOJ 3202 Second-price Auction

    Time Limit: 1 Second      Memory Limit: 32768 KB

    ShenduCC
  • Selenium Webdriver 在当前浏览器 Context 中 执行 JS 脚本。 Execute JavaScript based code using Selenium Webdriver

    In Selenium Webdriver, locators like XPath, CSS, etc. are used to identify and p...

    一个会写诗的程序员
  • TCP Flow Control

    TCP is the protocol that guarantees we can have a reliable communication channel...

    heidsoft
  • Selecting multiple checkboxes inside a GridView control

    Introduction GridView is a new data bound control introduced by Microsoft in Vis...

    阿新
  • Using k-NN for regression使用K-NN来做回归模型

    Regression is covered elsewhere in the book, but we might also want to run a reg...

    到不了的都叫做远方
  • SAP最佳业务实践:SD–带变式价格的销售报价(663)-4创建订单

    一、 VA01 Deriving Order from Follow-On Quotation Aftercomparing various quotation...

    SAP最佳业务实践
  • PsSetCreateProcessNotifyRoutineEx STATUS_ACCESS_DENIED IMAGE_DLLCHARACTERISTICS_FORCE_INTEGRITY

    PsSetCreateProcessNotifyRoutineEx 返回 STATUS_ACCESS_DENIED(0xC0000022L,即‭-1073741...

    战神伽罗
  • MySQL 聚集索引和二级索引

    Every InnoDB table has a special index called the clustered index where the data...

    JMCui

扫码关注云+社区

领取腾讯云代金券