UVa10618

  这道题不说什么了，自己编的，最后提交成功了。

// UVa 10618  
#include <cstdio> 
#include <cstring> 
using namespace std; 

const int maxn = 70 + 5; 
const int INF = 1000; // 1000 > 70 * 7
const char alpha[] = ".LR"; 

char s[maxn];
int opt[maxn][4][4][3][4]; 
int n, c[maxn], d[maxn][4][4][3];

int Energy(int olds, int s, int f, int t) {
  if (olds != s) return 1; 
  else {
    if (f == t) return 3; 
    else if ((f^1) != t) return 5;
    else return 7; 
  }
}

void update(int t1, int a1, int b1, int s1, int a2, int b2, int s2, int ch) {
  opt[t1][a1][b1][s1][0] = ch; 
  opt[t1][a1][b1][s1][1] = a2; 
  opt[t1][a1][b1][s1][2] = b2; 
  opt[t1][a1][b1][s1][3] = s2;
}

int dp(int t, int a, int b, int s) {
  int& ans = d[t][a][b][s]; 
  if (ans >= 0) return ans; 
  if (t == n) return ans = 0; 
  ans = INF; 
  if (c[t] == 4) {
    ans = dp(t+1, a, b, 0);
    update(t, a, b, s, a, b, 0, 0); 
    for (int i = 0; i < 4; ++i) if (i != a && i != b) {
      if (b != 2 && ans > dp(t+1, i, b, 1)+Energy(s, 1, a, i)) {
        ans = dp(t+1, i, b, 1)+Energy(s, 1, a, i);   
        update(t, a, b, s, i, b, 1, 1); 
      }
      if (a != 3 && ans > dp(t+1, a, i, 2)+Energy(s, 2, b, i)) {
        ans = dp(t+1, a, i, 2)+Energy(s, 2, b, i); 
        update(t, a, b, s, a, i, 2, 2); 
      }
    }
  } else {
    if ((a == c[t] || (a != c[t] && b != c[t] && b != 2)) && ans > dp(t+1, c[t], b, 1)+Energy(s, 1, a, c[t])) {
      ans = dp(t+1, c[t], b, 1)+Energy(s, 1, a, c[t]); 
      update(t, a, b, s, c[t], b, 1, 1);
    }
    if ((b == c[t] || (b != c[t] && a != c[t] && a != 3)) && ans > dp(t+1, a, c[t], 2)+Energy(s, 2, b, c[t])) {
      ans = dp(t+1, a, c[t], 2)+Energy(s, 2, b, c[t]);
      update(t, a, b, s, a, c[t], 2, 2);   
    }
  }
  return ans; 
}

void print_ans(int t, int a, int b, int s) {
  if (t == n) return; 
  printf("%c", alpha[opt[t][a][b][s][0]]);
  print_ans(t+1,opt[t][a][b][s][1],opt[t][a][b][s][2],opt[t][a][b][s][3]); 
}

int main() { 
  while (scanf("%s", s) == 1 && s[0] != '#') {
    n = strlen(s);
    for (int i = 0; i < n; ++i) {
      if (s[i] == '.') c[i] = 4;
      else if (s[i] == 'U') c[i] = 0;
      else if (s[i] == 'D') c[i] = 1;
      else if (s[i] == 'L') c[i] = 2; 
      else c[i] = 3;   
    }
    memset(d, -1, sizeof(d)); 
    dp(0, 2, 3, 0); 
    print_ans(0, 2, 3, 0); 
    printf("
");
  }
  return 0;
}