Hướng dẫn giải của Tháp Hà Nội


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include<iostream>
#include<algorithm>
#define fr(a,b,c) for (a=b;a<=c;a++)
using namespace std;

int main()
{
    int m,n,i,j,k;
    unsigned long long f[65][65];
    fr(i,1,64) f[1][i]=1;
    fr(i,2,64) f[i][3]=f[i-1][3]*2+1;
    fr(i,2,64)
     fr(j,4,64)
      if (i<=j-1) f[i][j]=2*i-1;
      else
      {
          f[i][j]=f[i][j-1];
          fr(k,1,i-1) f[i][j]=min(f[i][j],f[i-k][j-1]+f[k][j]*2);
      }
    while (cin >> n)
    {
          cin >> m;
          cout << f[n][m] << endl;
    }
    return 0;
}

Code mẫu của ladpro98

program chntower_dp;
uses    math;
const   fi='';
const   a:array[3..64] of int64 =(0,0,12582907,458745,65527,18421,7155,3825,2287,1645,1195,937,743,645,547,465,431,397,363,329,295,285,275,265,255,245,235,225,215,205,195,189,187,185,183,181,179,177,175,173,171,169,167,165,163,
161,159,157,155,153,151,149,147,145,143,141,139,137,135,133,131,129);
var     f:array[0..66,0..66] of qword;
        check:array[0..66,0..66] of boolean;
        m,n:longint;
        inp:text;

procedure init;
var     i:longint;
begin
        fillchar(f,sizeof(f),0);
        fillchar(check,sizeof(check),false);
        for i:=3 to 65 do
        begin
                f[0,i]:=0;
                check[0,i]:=true;
                f[1,i]:=1;
                check[1,i]:=true;
        end;

end;

function dp(n,p:longint):qword;
var     k:longint;
        //res:int64;

begin

        if check[n,p] then exit(f[n,p]);
        f[n,p]:=high(qword);
        if p = 3 then
        begin
                f[n,p]:=2*dp(n-1,3)+1;
                exit(f[n,p]);
                check[n,p]:=true;
        end;
        for k:=0 to n-1 do
        begin
                if f[n,p]>2*dp(k,p)+dp(n-k,p-1)
                then f[n,p]:=2*dp(k,p)+dp(n-k,p-1);

        end;
        //f[n,p]:=res;
        check[n,p]:=true;
        exit(f[n,p]);
end;

begin
        assign(inp,fi);
        reset(inp);
        init;
        while not eof(inp) do
        begin
        readln(inp,n,m);
        {if n = 64 then
        begin
                if m=3 then write('18446744073709551615')
                else if m=4 then write(18433)
                else write(a[m]);
                exit;
        end;  }

        writeln(dp(n,m));
        end;
end.

Code mẫu của RR

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
using namespace std;

const double PI = acos(-1.0);

unsigned ll f[66][66];

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    FOR(r,1,64) FOR(n,1,64) f[n][r] = 10001110001110001110ULL;

    f[1][2] = 1;
    FOR(r,3,64) {
        f[1][r] = 1;
        FOR(n,2,64) {
            f[n][r] = 2*f[1][r] + f[n-1][r-1];
            FOR(k,2,n-1)
                f[n][r] = min(f[n][r], 2*f[k][r] + f[n-k][r-1]);
        }
    }
    f[64][3] = 2*f[63][3] + 1;
    int n, k;
    while (cin >> n >> k)
        cout << f[n][k] << endl;
    return 0;
}

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>

int main()
{
    unsigned long long f[65][65],min=1;
    int n,k,a[65];

    for(int i = 1;i<=63;i++) min = min*2+1;
    for(int i = 0;i<=64;i++)
        for(int j = 0;j<=64;j++)
            f[i][j]=0;
    for(int j = 3;j<=64;j++)
    {
        for(int i =1;i<=j-2;i++)
            a[i]=0;
        f[1][j]=1;
        for(int i = 2;i<=64;i++)
        {  
                int flag = 0;
                unsigned long long Min = min;
                for(int t=1;t<=j-2;t++)
                {
                    if(f[a[t]+1][j-t+1]-f[a[t]][j-t+1]<Min)
                    {
                        Min = f[a[t]+1][j-t+1]-f[a[t]][j-t+1];
                        flag = t;
                    }
                }
                //if(j==3 &&i<10)printf("i=%d   Min=%llu   flag=%d\n",i,Min,flag);
                f[i][j]=f[i-1][j]+2*Min;
                a[flag]++;

        }
    }


   while(scanf("%d %d",&n,&k)>0)
    printf("%llu\n",f[n][k]);
   // getch();
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.