题意：给定N（1<= N <=64）个盘子和M（4<= M <= 65）根柱子，问把N个盘子从1号柱子移动到M号柱子所需要的最少步数，并且输出移动过程。
分析：设f[i][j]表示将i个盘通过j个柱子从第一根柱子移动到最后一根柱子所需要的最少次数，f[i][j]的得到的最优移动方案是先将最小的path[i][j]个盘移动到某一根柱子上，然后通过一个dfs输出移动次序。
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std; typedef unsigned long long LL;
const int N = ;
LL f[][];
// f[i][j]表示将i个盘通过j个柱子从第一根柱子移动到最后一根柱子所需要的最少次数
int path[][]; // 表示f[i][j]的得到的最优移动方案是先将最小的path[i][j]个盘移动到某一根柱子上
int n, m;
stack<int>stk[];
char ocp[]; void pre() {
memset(f, 0x3f, sizeof (f));
for (int i = ; i <= ; ++i) {
f[][i] = ;
f[][i] = ;
}
for (int i = ; i <= ; ++i) { // 初始化三根柱子的情况
f[i][] = f[i-][] * + ;
path[i][] = i-;
}
for (int i = ; i <= ; ++i) {
for (int j = ; j <= ; ++j) {
for (int k = ; k < i; ++k) {
if (f[i][j] > f[i-k][j-] + *f[k][j]) {
f[i][j] = f[i-k][j-] + *f[k][j];
path[i][j] = k;
}
}
}
}
}
/*
move 2 from 1 to 2
move 1 from 3 to 2 atop 2
*/ void display(int an, int am, int sta, int end) {
if (an == ) {
if (stk[end].size()) {
printf("move %d from %d to %d atop %d\n", stk[sta].top(), sta, end, stk[end].top());
} else {
printf("move %d from %d to %d\n", stk[sta].top(), sta, end);
}
stk[end].push(stk[sta].top());
stk[sta].pop();
return;
}
int peg = ;
for (int i = ; i <= m; ++i) {
if (i != sta && i != end && !ocp[i]) {
peg = i;
break;
}
}
display(path[an][am], am, sta, peg);
ocp[peg] = ;
display(an-path[an][am], am-, sta, end);
ocp[peg] = ;
display(path[an][am], am, peg, end);
} void solve() {
for (int i = ; i <= m; ++i) while (!stk[i].empty()) stk[i].pop();
for (int i = n; i >= ; --i) stk[].push(i);
memset(ocp, , sizeof (ocp));
printf("%llu\n", f[n][m]);
display(n, m, , m);
} int main() {
pre();
int T;
scanf("%d", &T);
while (T--) {
scanf("%d %d", &n, &m);
solve();
}
return ;
}