2017.11.3 N반 M주한노타 문제풀이DP 문제풀이 보고서

제목 설명
모두가 알다시피 한노타는 오래되고 고전적인 게임이다.이 게임은 이렇다. N개의 크기가 다른 접시와 3개의 기둥이 있다. 처음에는 모든 접시를 첫 번째 기둥에 겹쳐 놓아야 한다. N개의 접시를 모두 세 번째 기둥으로 옮겨야 한다. 매번 어떤 기둥의 맨 위에 있는 접시를 선택해서 다른 기둥으로 옮길 수 있다. 그러나 어느 때든지 접시 위에 그보다 큰 접시가 놓여 있지 않다는 것을 보증해야 한다.최소한의 이동 걸음 수를 구하세요.이 문제는 너무 간단하다. 도전을 즐기는 당신은 N개의 접시, M개의 기둥이 있고 다른 조건이 변하지 않을 때 모든 접시를 첫 번째 기둥에서 M개의 기둥으로 이동하는 최소한의 걸음수를 구하고 싶다.
입력 형식
한 줄의 두 정수는 각각 제목 중의 N, M을 대표한다.
출력 형식
한 줄의 정수가 답안을 대표한다.
예제
5 3 31
데이터 범위
10% 데이터의 경우 N <= 20, M = 3.30%의 데이터에 대해 M = 3.50% 데이터의 경우 M <= 4.100% 데이터의 경우 N <= 63, 3 <= M <= N + 1;
[문제풀이 보고]
기둥이 세 개밖에 없는 한노타를 비교하여 f[i][j]를 설치하여 i개의 접시와 j개의 기둥이 있을 때의 최소 걸음수를 나타낸다.그러면 틀림없이 위의 접시를 j가 아닌 기둥으로 옮기고 남은 접시를 j로 옮긴 다음에 위의 접시를 j로 옮긴다.그래서 점차적 f[i][j]=minf[k][j]\2+f[i-k][j-1]
코드는 다음과 같습니다.

#include
#include
#include
#include
using namespace std;
#define min(a,b) ((a)
#define LL long long
#define inf 0x3f3f3f3f
#define N 65

int n,m;
LL dp[N][N];

int main()
{
    freopen("hanoi.in","r",stdin);
    freopen("hanoi.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=0;ifor(int j=0;j3][0]=0;
    for(int i=1;i<=n;++i) dp[3][i]=dp[3][i-1]<<1|1;
    for(int i=4;i<=m;++i) dp[i][0]=0,dp[i][1]=1;
/*  for(int i=2;i<=n;++i)
    for(int j=1;j
    for(int i=4;i<=m;++i)
    for(int j=2;j<=n;++j)
    for(int k=1;k2+dp[i-1][k]);
    printf("%lld
",dp[m][n]);
    return 0;
}