蚂蚁316笔试

第三题，动态规划问题，状态：小红已经买了的食材类型，选择：位于可替代区间内的所有食材，dp[n]定义：购买完当前食材所需要的最小金额，事先定义食材类型-食材金额的哈希映射，加速查找过程。

import sys
n = int(sys.stdin.readline().strip())
k = int(sys.stdin.readline().strip())
food_type = list(map(int, sys.stdin.readline().strip().split()))
food_val = list(map(int, sys.stdin.readline().strip().split())) 

# 初始化dp数组 
dp=[float('inf')]*(n+1)
dp[0]=0

map =dict()
# 建立食物类型与食物价值的映射,便于后续查找
for i in range(n):
    type=food_type[i]
    val=food_val[i]
    map[type] = val

for i in range(1,n+1):
    low = food_type[i-1]-k
    up = k+food_type[i-1]
    cheap =float('inf')
    for type,val in map.items():  
        if low<=int(type)<=up:
            cheap = min(cheap,val)
    dp[i]=dp[i-1]+cheap
print(dp)
#笔试##技术岗笔试题求解#