AcWing--蜗牛--＞dp

5400. 蜗牛 - AcWing题库(python)

def get (x1,x2):
? ? if (x1<x2) :
? ? ? ? return (x2-x1)/0.7
? ? else:
? ? ? ? return (x1-x2)/1.3

# 输入

n=int(input())
# 初始化下标为1
x=list(map(int,input().split()))
x=[0]+x
a = [0] * n
b = [0] * (n + 1)

for i in range(1, n):
? ? input_data = input().split()
? ? a[i] = int(input_data[0])
? ? b[i + 1] = int(input_data[1])

# 定义dp状态方程
# 初始化
INF = float('inf')
f = [[INF] * 2 for _ in range(n + 1)]

# f（x,1)f(x,0)
f[1][0]=x[1]
for i in range (2,n+1):
? ? # 距离
? ? d=x[i]-x[i-1]
? ? # 1
? ? f[i][0]=min(f[i-1][0]+d,f[i-1][1]+get(b[i-1],0)+d)
? ? f[i][1]=min(f[i-1][0]+get(0,a[i-1]),f[i-1][1]+get(b[i-1],a[i-1]))
? ??
print("{:.2f}".format(min(f[n][0],f[n][1]+b[n]/1.3)))
? ??
? ??
? ??
? ??
? ??
? ??
? ??