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.
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