Editorial for Tháp Hà Nội


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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();
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.