本质上就是个简单的动规，但是各种条件限制太鬼畜了……

强行肝了大概四个多小时总算肝过去了，其中有三个小时是没发现输出代码有bug，一直在调已经对了的其他部分……

开四维数组f[决策步数][左脚位置][右脚位置][移动情况(不动|动左脚|动右脚)]=最小能量消耗，再开一个四维数组存储路径。

如果是‘.’那么枚举各种走法取最优方案，如果是按键，枚举左脚或者右脚去踩，取最优方案。

由于前一步的动作会影响到下一步的能量消耗，所以需要倒着动规。原本写了倒序循环的动规，在↑那心力交瘁的三个小时里改成了类DFS的形式……

代码写得很详细了：

1 //紫书P290   2 #include
     
        3 #include
      
         4 #include
       
          5 #include
        
           6 #include
         
            7 using namespace std;  8 const int mxn=90;  9 struct node{ 10     int l,r,last; 11 }ap[mxn][6][6][6]; 12 int f[mxn][6][6][6]; 13 //[已决策步数][左脚(上，下，左，右）][右脚（上，下，左，右）][上次移动脚(无，左，右)] 14 //                 0  1  2   3　　　　　　　　　　　　　　　　　　    0   1  2 15 char s[mxn]; 16 int n; 17 bool pd(int l,int r,int nl,int nr){
   //移动合法性判断 18     if(nl==l && nr==r)return 1; 19     if(nl==l)//左脚不动  20         if(nr!=l && l!=3)return 1; 21     if(nr==r)//右脚不动  22         if(nl!=r && r!=2)return 1; 23     return 0; 24 } 25 int cost(int f,int t,int last,int now){
   //起点，终点，上次移动脚，本次移动脚  26     if(last!=now)return 1;//无动作  27     if(f==t)return 3;//只踩不移动  28     if(f!=(t^1))return 5;//移动到相邻位置  29     return 7;//移动到相对位置  30 } 31 int dp(int i,int l,int r,int last){ 32     int& ans=f[i][l][r][last];//动规答案  33     node& a=ap[i][l][r][last];//路径 34     if(ans!=0x3f3f3f3f)return ans; 35     if(i==n)return ans=0;//到达起始状态，递归返回 36     if(s[i]=='.'){     37         //不移动 38         ans=min(ans,dp(i+1,l,r,0)); 39         a.l=l;a.r=r;a.last=0; 40         //四方向移动  41         for(int j=0;j<4;j++){ 42             //动左脚  43             if(pd(l,r,j,r)){ 44                 int tmp=dp(i+1,j,r,1)+cost(l,j,last,1); 45                 if(ans>tmp){ 46                     ans=tmp; 47                     a.l=j;a.r=r;a.last=1; 48                 } 49             } 50             //动右脚  51             if(pd(l,r,l,j)){ 52                 int tmp=dp(i+1,l,j,2)+cost(r,j,last,2); 53                 if(ans>tmp){ 54                     ans=tmp; 55                     a.l=l;a.r=j;a.last=2; 56                 } 57             } 58         } 59         return ans; 60     } 61 //    else{
     62     int dir=0;//目标移动方向  63     switch(s[i]){ 64         case 'L':{dir=2;break;} 65         case 'R':{dir=3;break;} 66         case 'U':{dir=0;break;} 67         case 'D':{dir=1;break;} 68     } 69      70     //动右脚  71     if(pd(l,r,l,dir)){ 72         int tmp=dp(i+1,l,dir,2)+cost(r,dir,last,2); 73         if(tmp
          
           0){ 94 if(last==0)printf("."); 95 else if(last==1)printf("L"); 96 else printf("R"); 97 } 98 nl=ap[i][tpl][tpr][last].l; 99 nr=ap[i][tpl][tpr][last].r;100 last=ap[i][tpl][tpr][last].last;101 }102 return;103 }104 int main(){105 int i,j;106 while(scanf("%s",s) && s[0]!='#'){107 memset(f,0x3f,sizeof f);108 n=strlen(s);109 dp(0,2,3,0);//从初始状态开始动规 110 Print();111 printf("\n");112 }113 return 0;114 }