首页 > ACM题库 > HDU-杭电 > HDU 1329 Hanoi Tower Troubles Again!-动态规划-[解题报告] C++
2013
12-09

HDU 1329 Hanoi Tower Troubles Again!-动态规划-[解题报告] C++

Hanoi Tower Troubles Again!

问题描述 :

People stopped moving discs from peg to peg after they know the number of steps needed to complete the entire task. But on the other hand, they didn’t not stopped thinking about similar puzzles with the Hanoi Tower. Mr.S invented a little game on it. The game consists of N pegs and a LOT of balls. The balls are numbered 1,2,3… The balls look ordinary, but they are actually magic. If the sum of the numbers on two balls is NOT a square number, they will push each other with a great force when they’re too closed, so they can NEVER be put together touching each other.

The player should place one ball on the top of a peg at a time. He should first try ball 1, then ball 2, then ball 3… If he fails to do so, the game ends. Help the player to place as many balls as possible. You may take a look at the picture above, since it shows us a best result for 4 pegs.

输入:

The first line of the input contains a single integer T, indicating the number of test cases. (1<=T<=50) Each test case contains a single integer N(1<=N<=50), indicating the number of pegs available.

输出:

For each test case in the input print a line containing an integer indicating the maximal number of balls that can be placed. Print -1 if an infinite number of balls can be placed.

样例输入:

2
4
25

样例输出:

11
337

2011-12-27 16:05:53

地址:http://acm.hdu.edu.cn/showproblem.php?pid=1329

题意:有n个棍子,依序从1开始放小球,两个相邻的球编号和必须是完全平方数。求最后一个能放下的序号。

mark:最多才1300,直接模拟。

代码:

# include <stdio.h>
# include <string.h>
# include <math.h>


int n ;
int dp[55] ;


int issquare(int a)
{
    int b = sqrt(1.0*a) ;
    return b*b == a ;
}


int gao()
{
    int i, j, flag ;
    for (i = 1 ; ; i++)
    {
        flag = 0 ;
        for (j = 0 ; j < n ; j++)
        {
            
            if (dp[j] == 0 || issquare (dp[j]+i))
            {
                dp[j] = i ;
                flag = 1 ;
                break ;
            }
        }
        if (flag == 0)
            return i-1 ;
    }
    return -1 ;
}


int main ()
{
    int T ;
    scanf ("%d", &T) ;
    while (T--)
    {
        scanf ("%d", &n) ;
        memset (dp, 0, sizeof(dp)) ;
        printf ("%d\n", gao()) ;
    }
    return 0 ;
}

解题报告转自:http://www.cnblogs.com/lzsz1212/archive/2012/01/06/2315393.html


  1. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

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

  3. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法