UVa 10618 跳舞机

这道题目题意很复杂，代码也是参考了别人的，因为自己实在是写不出。d[i][a][b][s]表示分析到第i个箭头时，此时左脚处于a，右脚处于b，上次移动的脚为s时的最小能量消耗。
  1 #include<iostream> 
  2 #include<cstring>
  3 #include<string>
  4 #include<algorithm>
  5 using namespace std;
  6 
  7 #define INF 10000000
  8 
  9 char str[105];
 10 int len;
 11 int d[105][4][4][3];
 12 int action[105][4][4][3];
 13 int pos[256];
 14 char place[] = ".LR";
 15 
 16 int energy(int a, int ta)
 17 {
 18     if (a == ta)  return 3;      //该脚没有移动
 19     if (a + ta == 3)  return 7;  //该脚移动到相对箭头
 20     return 5;                    //该脚移动到相邻箭头
 21 }
 22 
 23 int energy(int a, int b, int s, int f, int t, int& ta, int& tb)
 24 {
 25     ta = a;
 26     tb = b;
 27     //移动之后的脚的位置
 28     if (f == 1)   //左脚
 29         ta = t;
 30     if (f == 2)   //右脚
 31         tb = t;
 32     
 33     if (ta == tb)  return -1;              //移动之后两只脚在同一位置
 34     if (ta == 2 && tb == 1)  return -1;    //背向跳舞机状态
 35     if (a == 2 && tb != b) return -1;      //左脚在右箭头时，不能移动右脚
 36     if (b == 1 && ta != a)  return -1;     //右脚在左箭头时，不能移动左脚
 37 
 38     int e = 0;
 39     if (f == 0)           //没有移动
 40         e = 0;
 41     else if (f != s)      //和上个周期移动的脚不同
 42         e = 1;
 43     else
 44     {
 45         if (f == 1)
 46             e = energy(a, ta);
 47         else
 48             e = energy(b, tb);
 49     }
 50     return e;
 51 }
 52 
 53 void update(int i, int a, int b, int s, int f, int t)
 54 {
 55     int ta, tb;
 56     int e = energy(a, b, s, f, t, ta, tb);
 57     if (e < 0)    return;
 58     //逆推
 59     int cost = d[i + 1][ta][tb][f] + e;
 60     int& ans = d[i][a][b][s];
 61     if (ans>cost)
 62     {
 63         ans = cost;
 64         action[i][a][b][s] = f * 4 + t;
 65     }
 66 }
 67 
 68 int main()
 69 {
 70     //freopen("D:\txt.txt", "r", stdin);
 71     pos['U'] = 0;
 72     pos['D'] = 3;
 73     pos['L'] = 1;
 74     pos['R'] = 2;
 75     while (cin >> str)
 76     {
 77         if (str[0] == '#')    break;
 78         len = strlen(str);
 79         memset(d, 0, sizeof(d));
 80 
 81         //逆推导
 82         for (int i = len - 1; i >= 0; i--)
 83         {
 84             for (int a = 0; a < 4; a++)
 85             for (int b = 0; b < 4; b++)
 86             {
 87                 //两只脚不可能在同一箭头上
 88                 if (a == b)  continue;
 89                 for (int s = 0; s < 3; s++)
 90                 {
 91                     d[i][a][b][s] = INF;
 92                     if (str[i] == '.')
 93                     {
 94                         //不移动
 95                         update(i, a, b, s, 0, 0);
 96                         //任意往4个位置移动
 97                         for (int t = 0; t < 4; t++)
 98                         {
 99                             update(i, a, b, s, 1, t);
100                             update(i, a, b, s, 2, t);
101                         }
102                     }
103                     else
104                     {
105                         update(i, a, b, s, 1, pos[str[i]]);   //左脚移动到指定位置
106                         update(i, a, b, s, 2, pos[str[i]]);   //右脚移动到指定位置
107                     }
108                 }
109             }
110         }
111         //初始时左脚在左箭头，右脚在右箭头
112         int a = 1, b = 2, s = 0;
113         for (int i = 0; i < len; i++)
114         {
115             int f = action[i][a][b][s] / 4;
116             int t = action[i][a][b][s] % 4;
117             cout << place[f];
118             s = f;
119             if (f == 1)
120                 a = t;
121             else if (f == 2)
122                 b = t;
123         }
124         cout << endl;
125     }
126 }