https://ac.nowcoder.com/acm/contest/3004/I
题意: 输出汉诺塔移动过程中每一种移动的次数和移动总数.
如下
- A->B:XX
- A->C:XX
- B->A:XX
- B->C:XX
- C->A:XX
- C->B:XX
- SUM:XX
解法: 记忆化搜索, 当前状态的可以由上一状态得到.
- #include <cstdio>
- #include <cstring>
- #include <cmath>
- #include <algorithm>
- #include <iostream>
- #include <cstdio>
- #include <string>
- #include <stdio.h>
- #include <queue>
- #include <stack>
- #include <map>
- #include <set>
- #include <string.h>
- #include <vector>
- #define ME(x , y) memset(x , y , sizeof(x))
- #define SF(n) scanf("%d" , &n)
- #define rep(i , n) for(int i = 0 ; i <n ; i ++)
- #define INF 0x3f3f3f3f
- #define mod 998244353
- #define PI acos(-1)
- using namespace std;
- typedef long long ll ;
- const int maxn = 110;
- int n , m , k , t;
- struct node{
- ll ab , ac , ba , bc , ca , cb;
- }dp[maxn];
- bool vis[maxn];
- node hanio(int n , int a, int b , int c){
- if(vis[n]) return dp[n];
- node x = hanio(n-1 , a , c , b);
- dp[n].ab += x.ac;
- dp[n].ac += x.ab;
- dp[n].ba += x.ca;
- dp[n].ca += x.ba;
- dp[n].bc += x.cb;
- dp[n].cb += x.bc;
- dp[n].ac++;
- x = hanio(n-1 , b , a , c);
- dp[n].ab += x.ba;
- dp[n].ac += x.bc;
- dp[n].ba += x.ab;
- dp[n].ca += x.cb;
- dp[n].bc += x.ac;
- dp[n].cb += x.ca;
- vis[n] = 1;
- return dp[n];
- }
- int main()
- {
- vis[1] = 1 ;
- dp[1].ab = dp[1].ba = dp[1].bc = dp[1].ca = dp[1].cb = 0;
- dp[1].ac = 1 ;
- int n ; cin>> n;
- hanio(n , 1 , 2 , 3);
- ll sum = (1ll<<n)-1ll;
- cout <<"A->B:" <<dp[n].ab << endl;
- cout << "A->C:" <<dp[n].ac << endl;
- cout << "B->A:" <<dp[n].ba << endl;
- cout << "B->C:" <<dp[n].bc << endl;
- cout << "C->A:" <<dp[n].ca << endl;
- cout << "C->B:" << dp[n].cb << endl;
- cout << "SUM:" << sum << endl;
- return 0 ;
- }
也可打表找规律.
来源: http://www.bubuko.com/infodetail-3415663.html