SDRIVE - Lái xe
Tác giả: flashmt
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <cmath>
#define sqr(x) ((x)*(x))
using namespace std;
const double PI = 3.141592654;
int n, m, len[10010], type[10010];
double f[10010][22];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> type[i];
for (int i = 1; i <= n; i++) cin >> len[i];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
f[i][j] = 1e18;
if (!type[i])
{
for (int jj = 1; jj <= m; jj++)
if (abs(j - jj) * 100 <= len[i])
f[i][j] = min(f[i][j], f[i - 1][jj] + sqrt(sqr(len[i]) + sqr((j - jj) * 10)));
}
else
{
double radius = len[i] + 5;
if (type[i] == 1) radius += 10 * (j - 1);
else radius += 10 * (m - j);
f[i][j] = f[i - 1][j] + radius * PI * 0.5;
}
}
double ans = 1e18;
for (int j = 1; j <= m; j++) ans = min(ans, f[n][j]);
printf("%.2lf\n", ans);
}