| Problem Specification | Value |
|---|---|
| Time Limit | 1 Sec |
| Memory Limit | 162 MB |
| Submit | 1264 |
| Solved | 778 |
Description
汉诺塔由三根柱子 (分别用 A B C 表示) 和 n 个大小互不相同的空心盘子组成. 一开始 n 个盘子都摞在柱子 A 上, 大的在下面, 小的在上面, 形成了一个塔状的锥形体.
对汉诺塔的一次合法的操作是指: 从一根柱子的最上层拿一个盘子放到另一根柱子的最上层, 同时要保证被移动的盘子一定放在比它更大的盘子上面 (如果移动到空柱子上就不需要满足这个要求). 我们可以用两个字母来描述一次操作: 第一个字母代表起始柱子, 第二个字母代表目标柱子. 例如, AB 就是把柱子 A 最上面的那个盘子移到柱子 B. 汉诺塔的游戏目标是将所有的盘子从柱子 A 移动到柱子 B 或柱子 C 上面. 有一种非常简洁而经典的策略可以帮助我们完成这个游戏. 首先, 在任何操作执行之前, 我们以任意的次序为六种操作 (AB、AC、BA、BC、CA 和 CB) 赋予不同的优先级, 然后, 我们总是选择符合以下两个条件的操作来移动盘子, 直到所有的盘子都从柱子 A 移动到另一根柱子: (1) 这种操作是所有合法操作中优先级最高的; (2) 这种操作所要移动的盘子不是上一次操作所移动的那个盘子. 可以证明, 上述策略一定能完成汉诺塔游戏. 现在你的任务就是假设给定了每种操作的优先级, 计算按照上述策略操作汉诺塔移动所需要的步骤数.
Input
输入有两行. 第一行为一个整数 n (1≤n≤30), 代表盘子的个数. 第二行是一串大写的 ABC 字符, 代表六种操作的优先级, 靠前的操作具有较高的优先级. 每种操作都由一个空格隔开.
Output
只需输出一个数, 这个数表示移动的次数. 我们保证答案不会超过 10 的 18 次方.
Sample Input
3
AB BC CA BA CB ACSample Output
7HINT
Source
就考虑三个状态就行了:
我记得有一篇别的地方的博文讲了这几种情况的应对措施...... 在代码里应该也可以看到
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn = 40;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
int n, order[7], getfirst[7];
ll dp[maxn][4], dp2[maxn][4];
int theother(int _x, int _y)
{
return 6 - _x - _y;
}
int main(int argc, char** argv)
{
cin >> n;
for (int i = 1; i <= 6; i++) {
string tmp;
cin >> tmp;
order[i] = (tmp[0] - 'A') * 3 + (tmp[1] - 'A');
}
// Giving initial states of the 'dp'
for (int i = 6; i >= 1; i--)
dp2[1][order[i] / 3 + 1] = order[i] % 3 + 1;
for (int i = 1; i <= 3; dp[1][i] = 1, i++);
// (Main) Dynamic programming...
for (int i = 2; i <= n; i++) {
for (int x = 1; x <= 3; x++) {
int y = dp2[i - 1][x], z = theother(x, y);
if (dp2[i - 1][y] == z) {
dp[i][x] = dp[i - 1][x] + 1 + dp[i - 1][y];
dp2[i][x] = z;
} else {
dp[i][x] = dp[i - 1][x] + 1 + dp[i - 1][y] + 1 + dp[i - 1][x];
dp2[i][x] = y;
}
}
}
printf("%lld\n", dp[n][1]);
return 0;
}from pydatagen import *
n = randrange(2, 41)
a = randlist(6, ['AB', 'AC', 'BA', 'BC', 'CA', 'CB'], distinct=True)
printf('%d\n' % n)
print_oi(a)
fclose()