SRM557 Div1 Easy

250
貪欲に近い方へ移動する。
その後、その移動が正しいか確かめる。

class FoxAndMountainEasy {
public:
  string possible(int n, int h0, int hn, string history)
  {
    int U = 0;
    int D = 0;

    int h = h0;
    for (int i = 0; i < history.size(); ++i) {
      if (history[i] == 'U') ++h;
      else --h;
      --n;
    }
    while (n--) {
      int a = abs(hn - (h - 1));
      int b = abs(hn - (h + 1));
      if (a < b) {
        --h;
        --D;
      } else {
        ++h;
        ++U;
      }
    }
    if (h != hn) return "NO";
    h = h0 + U;
    for (int i = 0; i < history.size(); ++i) {
      if (history[i] == 'U') ++h;
      else --h;
      if (h < 0) return "NO";
    }
    return "YES";
  }
};