解题思路
part1
从上一状态走到$(x_n, 0)$的最短时间有两种方式:
1. 从$(x_{n-1}, 0)$直接走到$(x_n, 0)$。
2. 从$(x_{n-1}, a_{n-1})$经过传送门到$(x_n, b_{n-1})$再到$(x_n, 0)$。
part2
用动态规划
记录两种状态,$dp[i][0/1]$表示到$(i,0)$和$(i,a_i)$的最短时间。
时间复杂度:$O(n)$,具体细节参考代码部分。
参考代码
n = int(input())
x = [0] + list(map(int, input().split()))
op = [[]]
for _ in range(n - 1):
op.append(list(map(int, input().split())))
op.append([0, 0])
dp = [[0] * 2 for i in range(n + 1)]
dp[1][0] = x[1] # init dp
dp[1][1] = x[1] + op[1][0]/0.7
for i in range(2, n + 1):
dp[i][0] = min(dp[i-1][0] + x[i] - x[i-1], dp[i-1][1] + op[i-1][1]/1.3)
dp[i][1] = min(dp[i][0] + op[i][0]/0.7, dp[i-1][1] + \
abs(op[i-1][1] - op[i][0]) / (1.3 if op[i-1][1] >= op[i][0] else 0.7))
print("%.2f" % dp[n][0])
错误解法
从数据量来看,下面这个代码无论是内存还是时间都是会超的,$O(n^2)$。
如果数据量小的话,可以用这一种方法,$dp[i][j]$的含义就是到$(i,j)$的最短时间。
至于为什么放到这里来呢,因为一开始写的就是这个代码,不想白写,hhh。
n = int(input())
x = [0] + list(map(int, input().split()))
op = [[]]
for _ in range(n - 1):
op.append(list(map(int, input().split())))
op.append([0, 0])
dp = [[0] * (10**4 + 1) for i in range(n + 1)]
def get_y(y1, y2):
# distance from y1 yo y2
if y1 > y2: return (y1 - y2)/1.3
else: return (y2 - y1)/0.7
dp[1][0] = x[1]
dp[1][op[1][0]] = x[1] + op[1][0]/0.7
for i in range(2, n + 1):
for j in range(10**4 + 1):
if j > op[i][0]: continue
dp[i][j] = min(dp[i-1][0] + (x[i] - x[i-1]) + j/0.7, dp[i-1][op[i-1][0]] + get_y(op[i-1][1], j))
print("%.2f" % dp[n][0])