度小满笔试第二题
第一题的测试样例有点弱。直接print(9*（n-a+1）*(m-b+1))过了。
第二题暴力dp超时。过了18，不太清楚这道题能不能dp做。大佬们可以帮忙看看有什么问题吗，最后5分钟没来的及改成java，不知道java能不能过。
哭了，只能偷鸡。
N, A, B, C = map(int, input().split())
arr = list(map(int, input().split()))
# 到点i的最短的花费
dp = [float('inf')] * (N + 1)
# 起始点
dp[1] = 0
for i in range(N):
# 直接到达某城市
dp[arr[i]] = min(dp[arr[i]], A)
# 从该点可以到达的城市，减少到该点后一个城市
for k in range(i + 2, arr[i]):
dp[k] = min(dp[k], (arr[i] - k) * B + A + dp[i + 1])
# 从该点可以到达的城市，计算到第N个城市
for k in range(arr[i] + 1, N + 1):
dp[k] = min(dp[k], (k - arr[i]) * C + A + dp[i + 1])
print(dp[N]) 
拼多多集团-PDD公司氛围 517人发布
投递字节跳动等公司10个岗位 >