0419 百度笔试


有n座山每一座山的高度是H[i]
假设当前在i位置,接下来可以进行下面两个操作之一
1.走到相邻的山,代价是 min(0,H[j] - H[i])
2.发动闪现到任意位置 代价是p
2 <= n <=2e5
0<= p <= 1e9
0 <= H[i] <= 1e9
输入n和p,然后输入H[i]
输出走完所有山的最小代价
输入
6 5 
100 1 3 0 10 100
输出
7
解释
100 -> 1 代价0
1 -> 3 代价2
3 -> 100 代价5
100 ->10
输入
6 3 
1 1 10 10 100 100
输出
3
解释
闪现到最后然后走完所有山


#百度笔试##春招##实习##笔试题目#
全部评论
最小生成树,首先记录从第一个点与其右边点的时间耗费(建立一条边权重为两者差),并在出发点和其他各点建立一条权重为p的边,并按耗费排序,每次把当前位置加入树,利用并查集查询该点是否已存在,不存在则加入,否则跳过,最后计算最小生成树的权值就是答案
1 回复 分享
发布于 2022-04-20 09:48
动态规划,每座山(最前和最后的半山预处理掉)计算出从左到右和从右到左走的两种花费,然后dp[i][2]表示当前在第i座山当前走的方向为向左或者向右的最小花费,dp[i]从dp[i-1]转移,转移的时候注意i和i-1的方向不一致的转移要加上P
点赞 回复 分享
发布于 2022-04-30 00:12
请问有朋友收到下一步的通知了吗?我笔试完一直没动静,网申界面状态变成了“筛选中”
点赞 回复 分享
发布于 2022-04-29 14:47
楼主收到面试通知了吗
点赞 回复 分享
发布于 2022-04-20 22:27
直接骗分骗了16%,每个山取min(从左边到他,从右边到他,P)一定要用long!
点赞 回复 分享
发布于 2022-04-19 22:57
楼主有折纸那道题吗?记了吗,求
点赞 回复 分享
发布于 2022-04-19 22:23
回溯暴力过了10%😅
点赞 回复 分享
发布于 2022-04-19 22:13
蹲,这道题卡了一个小时
点赞 回复 分享
发布于 2022-04-19 22:09
蹲一个解法😥
点赞 回复 分享
发布于 2022-04-19 21:57

相关推荐

评论
1
7
分享

创作者周榜

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