SDRIVE - Lái xe

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>
#define REP(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)

const double INF = 1e9;
const double PI = 3.141592654;
const int N = 10101;
const int M = 22;

using namespace std;

void minimize(double &a, double b)
  { a = a > b ? b : a; }

double getLengthLine(int a, int b)
  { return sqrt(a * a + b * b); }

double getLengthCurve(int radius)
  { return PI * radius / 2; }

int n, m;
int type[N], s[N];
double dp[2][M];

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  #ifdef _LAD_
    freopen("SDRIVE.in", "r", stdin);
  #endif // _LAD_
  cin >> n >> m;
  REP(i, 1, n) cin >> type[i];
  REP(i, 1, n) cin >> s[i];
  int now = 0, nxt = 1;
  REP(i, 1, n) {
    REP(j, 1, m)
      dp[nxt][j] = INF;
    REP(j, 1, m) {
      if (type[i] == 0) {
        int range = s[i] / 100;
        REP(k, max(1, j - range), min(m, j + range))
          minimize(dp[nxt][k], dp[now][j] + getLengthLine(s[i], abs(j - k) * 10));
      } else if (type[i] == 1) {
        minimize(dp[nxt][j], dp[now][j] + getLengthCurve(s[i] + (j - 1) * 10 + 5));
      } else {
        minimize(dp[nxt][j], dp[now][j] + getLengthCurve(s[i] + (m - j) * 10 + 5));
      }
    }
    now ^= 1; nxt ^= 1;
  }
  double ans = INF;
  REP(i, 1, m)
    minimize(ans, dp[now][i]);
  cout << setprecision(2) << fixed << ans << endl;
  return 0;
}

Download