这个是汉诺塔的变形，思想和汉诺塔一样
但有一个很重要的是某两个点不能直接去，要经过第三个点，如果没用这种情况，递归方程很容易就写出来的。
在递归中，用s,t表示当前点从哪个点出发，到哪个点。如果S=-1，表示刚开始处理的点，如果T=-1，表示下面的点已经处理好了，这个点的目标任意（那肯定是要去自己想去的地方啦:) ）因此如果S,T都不为-1的话，就表示是在移动的过程中，这个点的移动只是为了让下面的点移动。因此可以将这个点以上的点看作是一条柱子来处理。计算出N个点一起从某个点到某个点移动的最小次数。
1 #include<stdio.h>
2 #include<iostream>
3 #include<string>
4 #include<vector>
5 #include<map>
6 #include<queue>
7 #include<algorithm>
8 #define M 1000
9 #define clr(x) memset(x,0,sizeof(x))
10 #define _clr(x) memset(x,-1,sizeof(x))
11 #define fr(i,a,b) for(int i=a;i<b;++i)
12 #define pf printf
13 #define sf scanf
14 #define pb push_back
15 #define mp make_pair
16 #define ll long long
17 #define debug 1
18 using namespace std;
19 int n;
20 struct person
21 {
22 int po,pt,p;
23 bool operator<(const person &a)const
24 {
25 return p<a.p;
26 }
27 }p[20];
28
29 ll dp[20][3][3];
30 int dfs1(int n,int s,int t)
31 {
32 if(dp[n][s][t])return dp[n][s][t];
33 if(n<=0)return 0;
34 if(n==1)
35 {
36 if(s+t==2)
37 return dp[n][s][t]=2;
38 else
39 dp[n][s][t]=1;
40 }
41 //return 1;
42 if(s+t==2)
43 {
44 return dp[n][s][t]=3*dfs1(n-1,s,t)+2;
45 }
46 return dp[n][s][t]=dfs1(n-1,s,3-s-t)+1+dfs1(n-1,3-s-t,t);
47 }
48 ll dfs(int cur,int s,int t)
49 {
50 if(cur==n)return 0;
51 int ss,tt;
52 if(s!=-1&&t!=-1)
53 {
54 //一栋的东西从某一个位置移到某一个位置
55 if(s==t)
56 {
57 ll tem=dfs(cur+1,s,t);
58 return tem;
59 }
60 else
61 {
62 ll tem=dfs1(n-cur,s,t);
63 return tem;
64 }
65 }
66 if(s==-1)ss=p[cur].po;
67 else ss=s;
68 if(t==-1)tt=p[cur].pt;
69 else tt=t;
70 if(ss==tt)
71 {
72 ll tem=dfs(cur+1,s,t);
73 return tem;
74 }
75 if(ss+tt==2)
76 {
77 ll tem=dfs(cur+1,s,tt)+1+dfs(cur+1,tt,ss)+1+dfs(cur+1,ss,t);;
78 return tem;
79 }
80
81
82 ll tem=dfs(cur+1,s,3-ss-tt)+1+dfs(cur+1,3-ss-tt,t);
83 return tem;
84
85 }
86 string s[2];
87 int getM(int pos)
88 {
89 if(s[pos][0]=='C')
90 {
91 if(s[pos][1]=='o')
92 return 0;
93 return 1;
94 }
95 return 2;
96 }
97 int main()
98 {
99 freopen("in.txt","r",stdin);
100 clr(dp);
101 while(sf("%d",&n)>0)
102 {
103 fr(i,0,n)
104 {
105 string point;
106 cin>>s[0]>>s[1]>>point;
107 p[i].po=getM(0);
108 p[i].pt=getM(1);
109 int a,b;
110 sscanf(point.c_str(),"%d.%d",&a,&b);
111 p[i].p=a*100+b;
112 //pf("po=%d pt=%d p=%d\n",po[i],pt[i],p[i]);
113 }
114 sort(p,p+n);
115 pf("%lld\n",dfs(0,-1,-1));
116 }
117 return 0;
118 }
119