09-11 21:00 已编辑 南京航空航天大学 C++ 发布于江苏
关注
华为机试
1+1+0.16
第三题基站通讯没啥思路#华为#
第三题基站通讯没啥思路#华为#
全部评论
牛客132353658号
东北大学 信息技术岗
佬，第二题什么思路啊？
牛客err
北京航空航天大学 C++
有题目嘛
中国电子云
校招火热招聘中
官网直投
black_zebra
浙江工商大学杭州商学院 Java
没啥思路是怎么0.16的，我只有0.03
牛客485316751号
华南理工大学 后端
贪心加dp，不太难，思路跟第二题类似。dp1到n，维护dp【i】，为到i号基站能赚的最多钱。
先对所有方案排序，基于每一个方案的r排序
排序完之后进行dp，
对于每一个位置
用一个now记录当前最小（指r最小）的方案，假设为J号方案吧从J.l到J.r号基站，赚J.val的钱
if（J.r>=i){
dp[i]=dp[i-1];//当前位置不能覆盖新的方案，那就数值没有变化
}else{//说明加入新的基站后至少有一个新的方案可以落实，
while（J.r==i）{//可能同时多个方案的r能加入
dp[i]=max(dp[i-1],dp[J.l-1]+J.val;//核心转移方程，如果加入当前方案，从当前方案的J.l左边一位转移过来。
}
}
得到dp【n】，输出即可。
相关推荐
投递华为等公司10个岗位 >
查看3道真题和解析 点赞 评论 收藏
分享