九连环问题
[PTA链接 ](https://pintia.cn/problem-sets/2066808699485880320/exam/problems/type/7?problemSetProblemId=2066808699527823367)
这个题目绝对不是目前这个层次的正常学生能做的，本身和汉诺塔问题有点像，难点在于如何分解这个问题为多个子问题，这个题目的条件初见是比较麻烦的，靠直接模拟是不太现实的，暴力的话时间复杂度会不够。所以只能看看找找规律了。
题目本身是有两种情况，全套上和全拆下，本质上这俩一样，只不过是相反的操作而已，这里我们分析全套上这种情况。可以把一个环的操作分为两种，套上和拆下，我们考虑当前环前面的环全部都空了（后面怎样都可以，因为条件没有限制后方），而且操作之后保证这个环之前还是空的。比如我们放 2 的话需要先放 1，为了保证操作之后 2 的前面是空的，所以整个操作就是 1U 2U 1D。
对于 1 而言，套上的话就直接 1U 即可，拆下的话就是 1D，对于 2 的话则是 1U 2U 1D，拆下是 1U 2D 1D，对于 3 的话则是 1U 2U 1D 3U 1U 2D 1D 和 1U 2U 1D 3D 1U 2D 1D，这时候能会发现一个事情，对于套上和拆家这两个操作操纵环的次序是相同的，如：1 2 1 3 1 2 1 和 1 2 1 3 1 2 1。而且对于 3 的套上和拆下本质上都是 2 套上 3U/D 2拆下，这种形式。
根据这个思想我们可以想起来，如果要放上 n 的话，就必须先放上 n - 1，而后的恢复前空还需要把 n - 1 给拆掉，n 的拆掉的话则同理，于是我们可以得到这个公式： n 的套上/拆带掉 = n - 1 的套上 nU/D n - 1的拆掉。这个就是我们的递推公式，根据这个公式写函数就可以得到一个一定正确的操作序列，但是这个序列不一定是最简的。因此我们还需要化简这个序列，观察这个函数求出的序列有很多是 2U 1U 1D 2D 这样的无用操作（即先放上去了，然后马上就拿下来了，这种操作我们肯定是不需要的），于是我们可以使用栈消掉这些无用操作，就可以得到最简操作。
代码如下：
```cpp
#include
#define first
#define second
// typedef pair PII;
char g[2] = {'U', 'D'};
int n, id, top;
char m;
struct Node
{
int a, b;
}e[10000];
void get(int x, int f)
{
if (x <= 0) return ;
get(x - 1, 0);
if (top && e[top].a == x && e[top].b != f) top -- ;
else e[ ++ top].a = x, e[top].b = f;
// printf("%d: %c\n", x, g[f]);
get(x - 1, 1);
}
int main()
{
scanf("%d %c", &n, &m);
// printf("%c\n", m);
if (m != 'U')
{
id = 1;
for (int i = 1; i <= n; i ++ )
{
get(i, id);
}
}
else
{
while (n)
{
get(n -- , id);
}
}
for (int i = 1; i <= top; i ++ )
{
int a = e[i].a, b = e[i].b;
printf("%d: %c\n", a, g[b]);
}
return 0;
}
```