SDRIVE - Lái xe
Tác giả: skyvn97
Ngôn ngữ: C++
#include<stdio.h>
#include<math.h>
#define PI acos(-1.0)
#define INF 1e9
double f[10101][22];
int s[10101];
int l[10101];
int n,m;
void init(void) {
int i;
scanf("%d",&n);
scanf("%d",&m);
for (i=1;i<=n;i=i+1) scanf("%d",&l[i]);
for (i=1;i<=n;i=i+1) scanf("%d",&s[i]);
}
int abs(int x) {
if (x<0) return (-x); else return (x);
}
double min(double a,double b) {
if (a<b) return (a); else return (b);
}
void optimize(void) {
int i,j,k;
for (i=1;i<=m;i=i+1) f[0][i]=0;
for (i=1;i<=n;i=i+1)
for (j=1;j<=m;j=j+1) {
if (l[i]==0) {
f[i][j]=INF;
for (k=1;k<=m;k=k+1)
if (abs(j-k)*100<=s[i])
f[i][j]=min(f[i][j],f[i-1][k]+hypot((j-k)*10,s[i]));
}
if (l[i]==1) f[i][j]=f[i-1][j]+PI*(s[i]+j*10-5)/2;
if (l[i]==2) f[i][j]=f[i-1][j]+PI*(s[i]+5+10*m-10*j)/2;
}
double r=INF;
for (i=1;i<=m;i=i+1)
if (f[n][i]<r) r=f[n][i];
printf("%.2lf",r);
}
int main(void) {
init();
optimize();
}