洛谷P1242 新汉诺塔题解

题意：

设有 $n$ 个大小不等的中空圆盘，按从小到大的顺序从 $1$ 到 $n$ 编号。将这 $n$ 个圆盘任意的迭套在三根立柱上，立柱的编号分别为 $A,B,C$，这个状态称为初始状态。

现在要求找到一种步数最少的移动方案，使得从初始状态转变为目标状态。

移动时有如下要求：

一次只能移一个盘；

不允许把大盘移到小盘上面。

输入格式：

第一行一个整数，状态中圆盘总数 $n$。

接下来三行每行若干个整数，分别代表初始状态下 $A,B,C$ 柱子上的圆盘从上到下的编号，如果只有一个数 $0$ 就代表这根柱子上没有数。

接下来三行每行若干个整数，分别代表目标状态下 $A,B,C$ 柱子上的圆盘从上到下的编号，如果只有一个数 $0$ 就代表这根柱子上没有数。

输出格式：

若干行每行一个字符串，格式为 move I from P to Q ，代表一个移动的操作。

接下来一行一个整数，代表从初始状态到目标状态的最少步数。

数据范围：

$1 \le n \le 45$ ，$1 $ 每个圆盘的编号 $\le n$ 。

每行的圆盘描述是从下到上的圆盘编号。

本来想写形式化一点的题解的，结果发现会变得异常晦涩难懂，因此本文还是通俗的讲解一下吧。

可以发现，最优方案中第一个摆正确的一定是第 $n$ 个圆盘。

于是可以~~很容易地~~写出下面的代码（这个代码是错误的）

int res,st[N], ed[N];
void move(int x, int y)
{
    if(st[x] == y) return;
    for(int i = x - 1; i >= 1; i--) move(i, 6 - (st[x] + y));
    cout << "move " << x << " from " << (char)(st[x] + 64) << " to " << (char)(y + 64) << '\n';
    st[x] = y; ++res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n, m; cin >> n;
    for(int i = 1; i <= 3; i++)
    {
        cin >> m;
        for(int j = 1, x; j <= m; j++) { cin >> x, st[x] = i; }
    }
    for(int i = 1; i <= 3; i++)
    {
        cin >> m;
        for(int j = 1, x; j <= m; j++) { cin >> x, ed[x] = i; }
    }
    for(int i = n; i; i--) move(i, ed[i]);
    cout << res << '\n';
    return 0;
}

为什么会错误呢？这里给出一组数据

在这种情况下，最优方案是这样的

move 4 from A to B （注意这一步）
move 1 from C to A
move 2 from C to B
move 1 from A to B
move 3 from C to A
move 1 from B to C
move 2 from B to A
move 1 from C to A
move 4 from B to C
9

这和我们刚才解法的区别在于，我们将第 $n$ 个圆盘移到非目标位置，然后完成前 $n-1$ 个，再一步把 $n$ 放好。

不妨称原来的解法为解法1，这个解法为解法2，他们的区别在于对于第 $n$ 个圆盘的处理不同。

在解法2中，值得琢磨的，就是应当用何种解法完成前 $n-1$ 个。

在上面的例子中，这 $n-1$ 个圆盘是叠在一起的，用解法1显然花费更少。

对于一般的情况，解法2使用一次解法1将 $n$ 移到非目标位置，这使得前 $n-1$ 个圆盘叠在一起

于是对于任何情况，我们实际上关心第 $n$ 个圆盘是否需要移动到非目标位置。

那么问题就解决了，我们完全可以把这两种情况都尝试一下，然后挑出最优的那个方案。

时间复杂度 $\mathcal{O}(2^n)$ ，不过题目肯定保证了输出方案不会超时（~~不然这题还做什么~~）

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(66))

char o[5] = {0, 'A', 'B', 'C'};
int cnt[2],sz[2][5],loc[2][N],now[2][N];
void move(int x, int st, int ed, int type, int ok)
{
    if(st == ed) return ;
    for(int i = x - 1; i >= 1; i--) move(i, now[0][i], 6 - (st + ed), type, ok);
    if(ok) cout << "move " << x << " from " << o[st] << " to " << o[ed] << '\n';
    else { ++cnt[type]; } now[0][x] = ed;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    for(int i = 1; i <= 3; i++)
    {
        cin >> sz[0][i];
        for(int j = 1, x; j <= sz[0][i]; j++) { cin >> x; loc[0][x] = i; }
    }
    for(int i = 1; i <= 3; i++)
    {
        cin >> sz[1][i];
        for(int j = 1, x; j <= sz[1][i]; j++) { cin >> x; loc[1][x] = i; }
    }
    memcpy(now, loc, sizeof(now));
    for(int i = n; i; i--) move(i, now[0][i], now[1][i], 0, 0);

    memcpy(now, loc, sizeof(now));
    move(n, now[0][n], 6 - (now[0][n] + now[1][n]), 1, 0);
    for(int i = n; i; i--) move(i, now[0][i], now[1][i], 1, 0);

    if(cnt[0] < cnt[1])
    {
        memcpy(now, loc, sizeof(now));
        for(int i = n; i; i--) move(i, now[0][i], now[1][i], 0, 1);
        cout << cnt[0] << '\n';
    }else
    {
        memcpy(now, loc, sizeof(now));
        move(n, now[0][n], 6 - (now[0][n] + now[1][n]), 1, 1);
        for(int i = n; i; i--) move(i, now[0][i], now[1][i], 1, 1);
        cout << cnt[1] << '\n';
    }
    return 0;
}