[UOJ #167]【UR #11】元旦老人与汉诺塔

题目大意：给你一个有$n$个盘子的汉诺塔状态$S$，问有多少种不同的操作方法，使得可以在$m$步以内到达状态$T$。$n,m\leqslant100$

题解：首先可以知道的是，一个状态最多可以转移到其他的$3$个状态，然后发现若$m\leqslant100$的话，每个柱子最多移动$7$个盘子，所以最多状态只有$3^{21}$次，这个数可能有点大，但是通过更严密的分析的话，最后状态数只有$10^5$级别，可以通过记忆化搜索通过。

卡点：妈啊，我怎么又把柱子上的顺序弄反了

 

C++ Code：

#include <cstdio> #include <iostream> #include <algorithm> #include <vector> #include <map> const int mod = 998244353; inline void reduce(int &x) { x += x >> 31 & mod; }int n, m, ans; std::vector<int> S, T, v[3]; std::map<std::vector<int>, int> f[105]; int dfs(int x, std::vector<int> S, std::vector<int> *v) {if (f[x].count(S)) return f[x][S];if (!x) return 0;int &F = f[x][S];for (int i = 0; i < 3; ++i) if (v[i].size())for (int j = 0; j < 3; ++j)if (!v[j].size() || v[i].back() < v[j].back()) {S[v[i].back()] = j;v[j].push_back(v[i].back()), v[i].pop_back();reduce(F += dfs(x - 1, S, v) - mod);S[v[j].back()] = i;v[i].push_back(v[j].back()), v[j].pop_back();}return F; } int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);std::cin >> n >> m;for (int i = 0, x; i < n; ++i) std::cin >> x, S.push_back(--x);for (int i = 0, x; i < n; ++i) std::cin >> x, T.push_back(--x);for (int i = n - 1; ~i; --i) v[T[i]].push_back(i);f[0][S] = 1;for (int i = 0; i <= m; ++i) reduce(ans += dfs(i, T, v) - mod);std::cout << ans << '\n';return 0; }

　　

转载于:https://www.cnblogs.com/Memory-of-winter/p/11354382.html

与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的[UOJ #167]【UR #11】元旦老人与汉诺塔的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。