本文主要是介绍Codeforces 392B Tower of Hanoi(递归+记忆化搜索），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：Codeforces 392B Tower of Hanoi
题目大意：给出一个3*3的矩阵，表示从i移动到j的代价，现在给出n，表示有n个碟子在1柱，需要移动到3柱，要求给出最小的花费。
解题思路：dp[l][r][n]，表示的是从l移动n个碟子到r的最小花费，然后总共有两种移动方式：
ans1 = solve(l, x, n-1) + solve(x, r, n-1) + val[l][r];
ans2 = solve(l, r, n-1)*2 + solve(r,l, n-1) + val[l][x] + val[x][r];
然后ans= min（ans1，ans2）。
需要注意的是最小的碟子移动时，比如最小的碟子要从1移动3需要100，移动到2再移动到3的花费是10，10.
#include <stdio.h>
#include <string.h>
#include <iostream>
#define min(a,b) (a)<(b)?(a):(b)using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 5;bool v[N][N][50];
ll val[N][N], best[N][N], dp[N][N][50];void init () {memset(v, 0, sizeof(v));for (int i = 1; i <= 3; i++)for (int j = 1; j <= 3; j++) {cin >> val[i][j];best[i][j] = val[i][j];}for (int i = 1; i <= 3; i++) {for (int j = 1; j <= 3; j++) {if (i == j) continue;for (int k = 1; k <= 3; k++) if (k != i && k != j) {best[i][j] = min(best[i][j], best[i][k] + best[k][j]);}}}
}ll solve(int l, int r, int n) {if (v[l][r][n]) return dp[l][r][n];v[l][r][n] = 1;ll& ans = dp[l][r][n];int x = 6 - l - r;if (n == 1) return ans = best[l][r];ans = solve(l, x, n-1) + solve(x, r, n-1) + val[l][r];ll k = solve(l, r, n-1) * 2 + solve(r, l, n-1) + val[l][x]+ val[x][r];ans = min(ans, k);return ans;
}int main () {init();int n;scanf("%d", &n);cout << solve(1, 3, n) << endl;return 0;
}
这篇关于Codeforces 392B Tower of Hanoi(递归+记忆化搜索）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
