解题思路:见注释
注意事项:
参考代码:
#include<bits/stdc++.h>
using namespace std;
#define maxm 2010
#define maxn 2010
typedef long long ll;
int n,m;
ll d;
ll a[maxn],b[maxm];
double dp[maxn][maxm][2];
//dp[i][j][0]是上面已经走了i个点,下面已经走了j个点,当前在上面
//对应的最小路程
//dp[i][j][1]是上面已经走了i个点,下面已经走了j个点,当前在下面
//对应的最小路程
int main(){
scanf("%d%d%lld",&n,&m,&d);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<=m;i++)scanf("%lld",&b[i]);
sort(a+1,a+1+n);
sort(b+1,b+1+m);
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
dp[i][j][0]=1e9;
dp[i][j][1]=1e9;
}
}
dp[0][0][0]=0;
dp[0][0][1]=0;
for(int i=1;i<=n;i++){
dp[i][0][0]=a[i];
}
for(int j=1;j<=m;j++){
dp[0][j][1]=d+b[j];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j][0]=min(dp[i-1][j][0]+a[i]-a[i-1],
dp[i-1][j][1]+sqrt(1.0*d*d+(a[i]-b[j])*(a[i]-b[j])));
dp[i][j][1]=min(dp[i][j-1][1]+b[j]-b[j-1],
dp[i][j-1][0]+sqrt(1.0*d*d+(a[i]-b[j])*(a[i]-b[j])));
}
}
printf("%.2lf",min(dp[n][m][0],dp[n][m][1]));
return 0;
}
0.0分
1 人评分
Hello, world! (C语言代码)浏览:1202 |
C语言程序设计教程(第三版)课后习题10.5 (C语言代码)浏览:1450 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:904 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:661 |
剪刀石头布 (C语言代码)浏览:753 |
Minesweeper (C语言描述,蓝桥杯)浏览:1127 |
核桃的数量 (C语言代码)浏览:672 |
C语言程序设计教程(第三版)课后习题9.8 (C语言代码)浏览:616 |
2006年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:345 |
用筛法求之N内的素数。 (C语言代码)浏览:532 |