한 노 타 II

http://acm.hdu.edu.cn/showproblem.php?pid=1207

한 노 타 II
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Problem Description
전형 적 인 한 노 타 문 제 는 항상 재 귀적 인 전형 적 인 예제 로 존재 한다.한 노 타 문제 의 전 고 를 모 르 는 사람 도 있 을 것 이다.한 노 타 는 인도 전설 에서 유래 한 이야기 로 하나님 이 세 계 를 창조 하 실 때 세 개의 금강석 기둥 을 만 들 었 고 한 기둥 에 아래 에서 위로 64 개의 황금 원반 이 쌓 여 있 었 다.하나님 은 브라만 에 게 원반 을 아래 부터 크기 순 으로 다른 기둥 위 에 다시 놓 으 라 고 명령 하 셨 다.또 작은 원반 에 서 는 원반 을 확대 할 수 없고 세 기둥 사이 에 서 는 한 번 에 한 개의 원반 만 움 직 일 수 있다 고 규정 했다.이 일이 완 성 될 때 우 주 는 순식간에 번개 처럼 멸망 할 것 이라는 예언 이 있다.브라만 이 아직도 원반 을 쉬 지 않 고 옮 기 고 있다 고 믿 는 사람 도 있다.응, 물론 이 전설 은 믿 을 수 없어. 지금 한 노 타 는 장난감 으로 더 많이 존재 해.가든 은 생일 선물 로 한 노 타 장난감 을 받 았 다.
Gardon 은 번 거 로 움 을 두려워 하 는 사람 입 니 다. (네, 게 으 름 을 잘 피 우 는 사람 입 니 다.) 모든 접시 가 세 번 째 기둥 에 도착 할 때 까지 64 개의 원반 을 하나씩 옮 기 는 것 이 어 려 운 것 이 분명 합 니 다. 그래서 Gardon 은 작은 폐단 을 하기 로 결 정 했 습 니 다. 그 는 똑 같은 기둥 을 찾 아 왔 습 니 다. 이 기둥 을 통 해 모든 접 시 를 세 번 째 기둥 으로 빨리 옮 겼 습 니 다.다음 문 제 는 Gardon 이 한 번 의 게임 에서 N 개의 접 시 를 사 용 했 을 때 그 는 몇 번 의 이동 이 있어 야 그들 을 세 번 째 기둥 으로 옮 길 수 있 습 니까?네 번 째 기둥 이 없 을 때 문제 의 해 는 2 ^ N - 1 인 것 이 분명 합 니 다. 하지만 지금 은 이 기둥 의 도움 이 있 으 면 얼마나 해 야 합 니까?

Input
여러 그룹의 데 이 터 를 포함 하고 모든 데이터 줄 은 접시 의 수량 N (1 < = N < = 64) 입 니 다.

Output
각 그룹의 데이터 에 대해 하나의 수 를 출력 하고 목표 에 도달 하 는 데 필요 한 최소 이동 수 입 니 다.

Sample Input

 
   
     1 3 12

Sample Output

1581

题意：

一个变形的汉诺塔——由3根柱改为4根，问最少移动步数。

思路：

这道题hdu有将近1k个AC，但是我还是想了一段时间（我太菜了！），一开始以为是留两块位置，一块给n-1，一块给n，所以总步数f[i] = 2f[i-2] + 3，但是过不了样例，想了好久没办法手推一下（我确实不想去敲个搜索），后来觉得可以是上面k块按4根柱子的玩，然后n-1-k块按3根柱子的玩。所以f[i] = 2min{f[k]+2^n-1-k-1}+1，结果过样例了。想了一下，应该是对的。后来AC证实这个应该没错！不过到底怎么证明这个玩法保证最少我就不懂怎么说了。

代码：

#include 
#include 
#include 
#include 
#include 
using namespace std;

#define MAXN 65
#define eps (1e-8)
#define INF 1000000000
#define abs(x) ( (x) > 0? (x): -(x) )
#define sqr(x) ((x) * (x))
#define MAX(a, b) ((a) > (b)? (a): (b))
#define MIN(a, b) ((a) < (b)? (a): (b))

typedef unsigned long long LL;

LL f[MAXN], g[MAXN];

void swap( int &x, int &y ) { int temp = x; x = y; y = temp; }

int main()
{
    int n;
    f[0] = g[0] = 0;
    f[1] = g[1] = 1; 
    f[2] = g[2] = 3;
    for ( int i = 3; i < MAXN; ++i ) 
    {
        f[i] = g[i] = g[i - 1] * 2 + 1;
        for ( int j = 1; j < i; ++j )
            f[i] = MIN( f[i], 2 * ( f[j] + g[i - j - 1] ) + 1 );
    }
    while ( scanf( "%d", &n ) != EOF ) printf( "%lld
", f[n] );
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

hdu 1233 절 대 컴퓨터 대학원 재시험

모 성에 서 마을 의 교통 상황 을 조사 하여 얻 은 통계표 에는 임의의 두 마을 간 의 거리 가 열거 되 어 있다.성 정부의 '원활 한 공사' 목 표 는 성 전체의 어느 두 마을 간 에 도 도로 교통 을 실현 할 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

한 노 타 II

좋은 웹페이지 즐겨찾기