SRM538 Div1 Medium

450

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

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

view plainprint?

1. class TurtleSpy {  
2. public:  
3.   double maxDistance(vector <string> C)  
4.   {  
5.     vector<int> A;  
6.   
7.     double F = 0;  
8.     double B = 0;  
9.     for (int i = 0; i < (int)C.size(); ++i) {  
10.       istringstream iss(C[i]);  
11.       string c;  
12.       int n;  
13.       iss >> c >> n;  
14.       if (c[0] == 'f') F += n;  
15.       if (c[0] == 'b') B += n;  
16.       if (c[0] == 'l') A.push_back(n);  
17.       if (c[0] == 'r') A.push_back(360 - n);  
18.     }  
19.   
20.     const int N = A.size() + 1;  
21.     const int M = 360 + 1;  
22.     bool dp[N][M];  
23.     fill(&dp[0][0], &dp[N - 1][M], false);  
24.     dp[0][0] = true;  
25.   
26.     for (int i = 0; i < (int)A.size(); ++i) {  
27.       for (int j = 0; j < (int)M; ++j) {  
28.         if (dp[i][j]) {  
29.           dp[i + 1][j] = true;  
30.           dp[i + 1][(j + A[i]) % 360] = true;  
31.         }  
32.       }  
33.     }  
34.   
35.     double mx = 0;  
36.   
37.     for (int i = 0; i < (int)M; ++i) {  
38.       if (!dp[A.size()][i]) continue;  
39.       double a = M_PI / 180.0 * i;  
40.       double d = F * F + B * B - 2.0 * F * B * cos(a);  
41.       mx = max(mx, sqrt(d));  
42.     }  
43.   
44.     return mx;  
45.   }  
46. };  

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;
  }
};