2010-1080
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
== Sulotion report by asmn. ==
题目的模型就是有一个有不超过19个盘子的三个柱子的汉诺塔，给出盘子初始所在的位置和期望在的位置，问至少多少步能转移到，与基本的汉诺塔不同之处就是每个盘子都只能移到它旁边的柱子上，即不能在第一根柱子和第三根柱子间互相移动。
解题的基本思路就是要先让最大的盘子（在题目中也就是成绩最差的学生）先到达其期望到的位置。最大的盘子移好后，剩下的盘子移动时就完全不用考虑这个大盘子的影响，于是把问题归约至较小规模的问题，递归解决。
要使最大的盘子从一根柱子移到相邻的另一根柱子，必须先把其他所有的盘子移到除了大盘子所在位置的柱子和期望移动到的位置上。如果一步步模拟的话，会因为步数过多而超时，所以当要把一根柱子上的连续的一堆盘子移动到另一根柱子的时候，可以用公式来计算。
F(n)表示把一根柱子上的连续n个盘子移到相邻的柱子上所需的步数。
G(n)表示把第一根柱子上的连续n个盘子移到第三根（或者反过来移动）所需的步数。
则可以用递推式来求出它们的值。
{{{
F(1) = 1
F(n) = G(n - 1) + F(n - 1) + 1 n > 1
G(1) = 2
G(n) = G(n - 1) * 3 + 2 n > 1
}}}
程序解释：
struct node里面保存的now表示当前盘子所在的位置，to表示它期望到达的位置，score表示学生的成绩。
gao(k) 求把编号为0~k的盘子放到正确的位置所需的步数。
allgo(k, to)求把编号为0~k的盘子都放到to那个柱子上所需的步数。
{{{
#!cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
typedef long long LL;
struct node{
int now, to;
double score;
}P[20];
LL F[20], G[20];
map <char, int> num;
inline bool operator <(node p1, node p2){
return p1.score > p2.score;
}
LL allgo(int k, int to){
if (k < 0)
return 0;
if (P[k].now == to)
return allgo(k - 1, to);
bool all = true;
LL ret = 0;
for (int i = 0; i < k; ++i)
if (P[i].now != P[k].now)
all = false;
if (all){
switch(abs(P[k].now - to)){
case 1:
ret += F[k + 1];
break;
case 2:
ret += G[k + 1];
break;
}
for (int i = 0; i <= k; ++i)
P[i].now = to;
} else {
while (P[k].now != to){
switch(P[k].now){
case 0: case 2:
ret += allgo(k - 1, 2 - P[k].now) + 1;
P[k].now = 1;
break;
case 1:
ret += allgo(k - 1, 2 - to) + 1;
P[k].now = to;
break;
}
}
ret += allgo(k - 1, to);
}
return ret;
}
LL gao(int k){
if (k < 0)
return 0LL;
LL ret = 0LL;
while (P[k].now != P[k].to){
switch(P[k].now){
case 0:
case 2:
ret += allgo(k - 1, 2 - P[k].now) + 1;
P[k].now = 1;
break;
case 1:
ret += allgo(k - 1, 2 - P[k].to) + 1;
P[k].now = P[k].to;
break;
}
}
return ret + gao(k - 1);
}
void init(void){
num['o'] = 0;
num['h'] = 1;
num['a'] = 2;
F[1] = 1;
G[1] = 2;
for (int i = 2; i < 20; ++i){
F[i] = G[i - 1] + F[i - 1] + 1;
G[i] = G[i - 1] * 3 + 2;
}
}
int main(){
int N, i;
string s;
init();
while(scanf("%d", &N) != EOF){
for (i = 0; i < N; ++i){
cin >> s;
P[i].now = num[s[1]];
cin >> s;
P[i].to = num[s[1]];
cin >> P[i].score;
}
sort(P, P + N);
cout << gao(N - 1) << endl;
}
return 0;
}
}}}
----Sulotion report by asmn.
题目的模型就是有一个有不超过19个盘子的三个柱子的汉诺塔，给出盘子初始所在的位置和期望在的位置，问至少多少步能转移到，与基本的汉诺塔不同之处就是每个盘子都只能移到它旁边的柱子上，即不能在第一根柱子和第三根柱子间互相移动。
解题的基本思路就是要先让最大的盘子（在题目中也就是成绩最差的学生）先到达其期望到的位置。最大的盘子移好后，剩下的盘子移动时就完全不用考虑这个大盘子的影响，于是把问题归约至较小规模的问题，递归解决。
要使最大的盘子从一根柱子移到相邻的另一根柱子，必须先把其他所有的盘子移到除了大盘子所在位置的柱子和期望移动到的位置上。如果一步步模拟的话，会因为步数过多而超时，所以当要把一根柱子上的连续的一堆盘子移动到另一根柱子的时候，可以用公式来计算。
F(n)表示把一根柱子上的连续n个盘子移到相邻的柱子上所需的步数。
G(n)表示把第一根柱子上的连续n个盘子移到第三根（或者反过来移动）所需的步数。
则可以用递推式来求出它们的值。
F(1) = 1
F(n) = G(n - 1) + F(n - 1) + 1 n > 1
G(1) = 2
G(n) = G(n - 1) * 3 + 2 n > 1
程序解释：
struct node里面保存的now表示当前盘子所在的位置，to表示它期望到达的位置，score表示学生的成绩。
gao(k) 求把编号为0~k的盘子放到正确的位置所需的步数。
allgo(k, to)求把编号为0~k的盘子都放到to那个柱子上所需的步数。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
typedef long long LL;
struct node{
int now, to;
double score;
}P[20];
LL F[20], G[20];
map <char, int> num;
inline bool operator <(node p1, node p2){
return p1.score > p2.score;
}
LL allgo(int k, int to){
if (k < 0)
return 0;
if (P[k].now == to)
return allgo(k - 1, to);
bool all = true;
LL ret = 0;
for (int i = 0; i < k; ++i)
if (P[i].now != P[k].now)
all = false;
if (all){
switch(abs(P[k].now - to)){
case 1:
ret += F[k + 1];
break;
case 2:
ret += G[k + 1];
break;
}
for (int i = 0; i <= k; ++i)
P[i].now = to;
} else {
while (P[k].now != to){
switch(P[k].now){
case 0: case 2:
ret += allgo(k - 1, 2 - P[k].now) + 1;
P[k].now = 1;
break;
case 1:
ret += allgo(k - 1, 2 - to) + 1;
P[k].now = to;
break;
}
}
ret += allgo(k - 1, to);
}
return ret;
}
LL gao(int k){
if (k < 0)
return 0LL;
LL ret = 0LL;
while (P[k].now != P[k].to){
switch(P[k].now){
case 0:
case 2:
ret += allgo(k - 1, 2 - P[k].now) + 1;
P[k].now = 1;
break;
case 1:
ret += allgo(k - 1, 2 - P[k].to) + 1;
P[k].now = P[k].to;
break;
}
}
return ret + gao(k - 1);
}
void init(void){
num['o'] = 0;
num['h'] = 1;
num['a'] = 2;
F[1] = 1;
G[1] = 2;
for (int i = 2; i < 20; ++i){
F[i] = G[i - 1] + F[i - 1] + 1;
G[i] = G[i - 1] * 3 + 2;
}
}
int main(){
int N, i;
string s;
init();
while(scanf("%d", &N) != EOF){
for (i = 0; i < N; ++i){
cin >> s;
P[i].now = num[s[1]];
cin >> s;
P[i].to = num[s[1]];
cin >> P[i].score;
}
sort(P, P + N);
cout << gao(N - 1) << endl;
}
return 0;
}