#include<iostream> #include<algorithm> #include<cstring> #include<cmath> using namespace std ; typedef long long LL ; struct edge{ double x , y ; };//定义点 , 把每一个位置换成坐标 方便计算距离 const int N = 510 ; int L , R ; edge l[N] ,r[N] ;//记录左右两边每一个的距离 double d, w ; double f[N][N][2] ;//开三维数组,表示左边整理了i副右边整理了j副切最后一个落点再左边或者右边的最短距离 double dd(edge a, edge b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)) ; }//用于计算距离 int main(){ cin >> L >> R >> d >> w ; for(int i = 1 ; i <= L ; i ++){ l[i].x = 0 ;cin >> l[i].y ;//画廊左侧 } for(int j = 1 ; j <= R ; j ++) { r[j].x = w ;cin >> r[j].y ;//画廊右侧 } edge a ; a.x = w/2 ; a.y = 0 ;//定义起点,即画廊起点中央位置 edge b ; b.x = w/2 ; b.y = d ;//定义终点,即画廊终点中央位置 memset(f,127 , sizeof f) ;//要取最小值先初始化数组 //关于memset初始化double注意一下 f[1][0][0] = dd(l[1] , a) ;//起点跳到第一个左边画廊的距离 f[0][1][1] = dd(r[1] , a) ;//起点跳到第一个右边画廊的距离 for(int i = 0 ; i <= L ; i ++){//必须从第一个数开因为可以一直跳画廊左边 for(int j = 0 ; j <= R ; j ++){//必须从第一个数开因为可以一直跳画廊右边 //1.f[i][j][0/1] 要参与判断的原因是当i=1,j=0时f[1][0][0]就变值了 //2.f[i-1][j][0] 一共就两种变化的情况 要不然从同行来 ,要不然从对侧来 if(i) f[i][j][0] = min( f[i][j][0],min(f[i-1][j][0] + dd(l[i-1] , l[i] ) ,f[i-1][j][1] + dd(l[i],r[j]) )); if(j) f[i][j][1] = min( f[i][j][1],min(f[i][j-1][1] + dd(r[j-1] , r[j] ) ,f[i][j-1][0] + dd(l[i],r[j]) )); } } double ans = 0 ; //最后落点落在最后两侧的最小值加上到终点的距离就是最终距离 ans = min(f[L][R][0] + dd(l[L] , b) , f[L][R][1] + dd(r[R] , b)) ; printf("%.2lf",ans) ; return 0 ; }
注意一下memset对double的使用