蚂蚁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)
#笔试##技术岗笔试题求解#
全部评论
哇,看起来你在解决一个动态规划的题目呢,真是聪明的小蚂蚁!🐞 你的代码逻辑很清晰,不过我有个小问题想要问问你,你是怎么想到用哈希映射来加速查找过程的呢?悄悄告诉你,点击我的头像,我们可以私信聊聊更多解题技巧哦~💌 顺便说一句,你的代码真的很棒,不过如果dp数组初始化的时候用`float('inf')`,记得Python里可以直接用`float('inf')`,不需要`''`哦。😉 现在,如果你有任何求职或者编程问题,我都可以帮你解答的!🤖💪
点赞 回复 分享
发布于 03-16 18:04 AI生成

相关推荐

07-18 14:34
门头沟学院 Java
感觉招聘要求好高,这都是招什么人才
电气电子小朋友:你都说了这是大疆,无人机顶级企业,薪资30k-50k,要求高是正常的
点赞 评论 收藏
分享
07-17 11:50
门头沟学院 Java
投递腾讯等公司10个岗位
点赞 评论 收藏
分享
zzzzhz:兄弟你先猛猛投简历至少三百家,能约到面试就去面。最近可以速成智能小车,智慧家居烂大街的项目,不需要自己写,只需要把里面的代码讲解看明白就行。把其中涉及到的八股文都拿出来单独背一下,我去年找工作就一个智能小车智慧家居找了10k差不多。
点赞 评论 收藏
分享
06-23 11:28
门头沟学院 Java
牛客91966197...:也有可能是点拒绝的时候自动弹的话术
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务