第三题，动态规划问题，状态：小红已经买了的食材类型，选择：位于可替代区间内的所有食材，dp[n]定义：购买完当前食材所需要的最小金额，事先定义食材类型-食材金额的哈希映射，加速查找过程。import sysn = 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]=0map =dict()# 建立食物类型与食物价值的映射,便于后续查找for i in range(n):type=food_type[i]val=food_val[i]map[type] = valfor i in range(1,n+1):low = food_type[i-1]-kup = 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]+cheapprint(dp)