解题思路

用$dp[i][x][y][z]$表示已经踩了$i$个箭头，目前左脚在$x$上，右脚在$y$上，刚才这一步步【第$i$步】移动的是$z$脚，还需要多少能量才能完成。 根据是否有箭头和箭头的方向，枚举下一步的移动并计算费用。

标程

#include<cstdio>
#include<cstring>
int dp[75][10][10][5],next_f[75][10][10][5],next_d[75][10][10][5],n,a[75];
char s[75];
int cost(int x,int y)
{
    if (x==y) return 3;
    if (x+y==3||x+y==7) return 7;
    return 5;
}
void upd(int sta,int L,int R,int pre,int val,int mv_f,int next_p)
{
    if (val<dp[sta][L][R][pre])
    {
        dp[sta][L][R][pre]=val;
        next_f[sta][L][R][pre]=mv_f;
        next_d[sta][L][R][pre]=next_p;
    }
}
void prt(int p,int L,int R,int pre)
{
    if (p==n) return;
    switch (next_f[p][L][R][pre])
    {
        case 0:printf(".");prt(p+1,L,R,0);break;
        case 1:printf("L");prt(p+1,next_d[p][L][R][pre],R,1);break;
        case 2:printf("R");prt(p+1,L,next_d[p][L][R][pre],2);break;
    }
}
int main()
{
    int i,j,k,p,q,x,y,z,u,v,w;
    while (scanf("%s",s+1)&&s[1]!='#')
    {
        n=strlen(s+1);
        for (i=1;i<=n;i++)
          switch (s[i]) 
          {
            case '.':a[i]=0;break;
            case 'L':a[i]=1;break;
            case 'R':a[i]=2;break;
            case 'U':a[i]=3;break;
            case 'D':a[i]=4;break;
          }
        memset(dp,0x3f,sizeof(dp));
        for (x=1;x<=4;x++)
          for (y=1;y<=4;y++)
            for (z=0;z<=2;z++)
              dp[n][x][y][z]=0;
        for (i=n-1;i>=0;i--)
          for (x=1;x<=4;x++)
            for (y=1;y<=4;y++)
              if (x!=y)
                for (z=0;z<=2;z++)
                  if (a[i+1]==0)
                  {
                      upd(i,x,y,z,dp[i+1][x][y][0],0,0);
                      for (w=1;w<=4;w++)
                      {
                        if (w!=y&&(y!=1||w==x))
                          upd(i,x,y,z,dp[i+1][w][y][1]+ (z==1?cost(w,x):1),1,w);
                        if (w!=x&&(x!=2||w==y))
                          upd(i,x,y,z,dp[i+1][x][w][2]+ (z==2?cost(w,y):1),2,w);
                      }
                  }
                  else
                  {
                    w=a[i+1];
                    if (w!=y&&(y!=1||w==x))
                      upd(i,x,y,z,dp[i+1][w][y][1]+ (z==1?cost(w,x):1),1,w);
                    if (w!=x&&(x!=2||w==y))
                      upd(i,x,y,z,dp[i+1][x][w][2]+ (z==2?cost(w,y):1),2,w);
                  }
        prt(0,1,2,0);
        printf("\n");
    }
}