SRM538 Div1 Medium

450

何度も曲がるのは最適でない。
最初に前進を全て使った後、いくらか曲がって後進を使う。

余弦定理が出てこなくて少し焦った。

class TurtleSpy {
public:
  double maxDistance(vector <string> C)
  {
    vector<int> A;

    double F = 0;
    double B = 0;
    for (int i = 0; i < (int)C.size(); ++i) {
      istringstream iss(C[i]);
      string c;
      int n;
      iss >> c >> n;
      if (c[0] == 'f') F += n;
      if (c[0] == 'b') B += n;
      if (c[0] == 'l') A.push_back(n);
      if (c[0] == 'r') A.push_back(360 - n);
    }

    const int N = A.size() + 1;
    const int M = 360 + 1;
    bool dp[N][M];
    fill(&dp[0][0], &dp[N - 1][M], false);
    dp[0][0] = true;

    for (int i = 0; i < (int)A.size(); ++i) {
      for (int j = 0; j < (int)M; ++j) {
        if (dp[i][j]) {
          dp[i + 1][j] = true;
          dp[i + 1][(j + A[i]) % 360] = true;
        }
      }
    }

    double mx = 0;

    for (int i = 0; i < (int)M; ++i) {
      if (!dp[A.size()][i]) continue;
      double a = M_PI / 180.0 * i;
      double d = F * F + B * B - 2.0 * F * B * cos(a);
      mx = max(mx, sqrt(d));
    }

    return mx;
  }
};