dp ；
我们设状态表示，f[N][2] 表示到第i个杆的底部和传送门位置所需要的最短路程；
对于f[i][0] 有两种可以转换的方程
一种是由f[i-1][0]走过来，f[i][0] = f[i-1][0] +d(两杆之间的直接距离)
二种是由f[i-1][1]走过来,f[i][0] = f[i-1][1] + b[i] /1.3
对于f[i][1] 有两种可以转换的方程
一种是由f[i-1][0] 走过来，f[i][1] = f[i-1][0]+d+a[i]/0.7
二种是由f[i-1][1] 走过俩，f[i][1] = f[i-1][1] + (b - a) / 速度
#include<iostream> #include<cstring> #include<algorithm> using namespace std ; const int N = 1e5+10; double f[N][2] ; double x[N] ,a[N],b[N] ; int n ; int main(){ cin >> n ; for(int i = 1 ; i<= n ; i++) cin >> x[i] ; for(int i = 1 ; i < n ; i++) cin >> a[i] >> b[i] ; memset(f,127,sizeof(f)) ; f[1][0] = x[1] ; f[1][1] = f[1][0] + a[1] / 0.7; for(int i = 2; i <= n ;i ++){ f[i][0] = min(f[i-1][0]+x[i]-x[i-1] ,f[i-1][1] + b[i-1] / 1.3 ) ; f[i][1] = min(f[i][0] + a[i]/0.7 , f[i-1][1] + abs(b[i-1]- a[i]) / (b[i-1] >= a[i] ? 1.3:0.7 )); } printf("%.2f\n",f[n][0]) ; }
