鸵鸟的仰望
2020-03-29 23:45 中国科学技术大学 Java
关注
首先考虑n等于m的情况，这时候每个数字都会选，则进项确定，不确定的是代价（被减去的值），这时候策略是比较简单的，代价（bi）越大的值越先选……。
然后考虑n=m+1时候的情况，这个问题相比前一个问题就是要剔除一个值了，这时候可以看成一个递增的问题，即先处理m个，再考虑最后一个。这时候先把前m个值按照bi排序，再计算第m+1个元素取代第i个元素的增益，如果最大增益能大于0，则取代并更新备用的数组，否则备用数组不动（这部分就算按照一定策略，时间复杂度o（n）），备用数组就是我们选择的m个数，按照第一个问题的策略，能得出此时的结果。
最后，考虑n>m+1，这时候能不能分解成一系列n=m+1的子问题？？？如果能分解的话，就按照前一步的步骤就可以计算了
查看原帖
点赞 评论
相关推荐
腾讯公司福利 832人发布 点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-13 19:30
苦闷的柠檬精allin实习：主管面结束后hr每周保温一次，结果前几天和我说没hc了，我也化身华黑子了
投递华为等公司8个岗位 > 华为求职进展汇总 点赞 评论 收藏
分享
06-09 19:55
郑州大学 算法工程师 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 职场捅娄子大赛 #
370970次浏览 3784人参与
# 找实习你看重大厂光环还是业务方向 #
11699次浏览 89人参与
# 写给毕业5年后的自己 #
13506次浏览 241人参与
# 你的房租占工资的比例是多少？ #
29787次浏览 333人参与
# 考研对你找工作产生了哪些影响？ #
17398次浏览 152人参与
# 你最满意的offer薪资是哪家公司？ #
27525次浏览 149人参与
# 什么专业适合考公 #
32351次浏览 207人参与
# 听到哪句话就代表面试稳了or挂了？ #
166662次浏览 1345人参与
# 每人推荐一个小而美的高薪公司 #
74650次浏览 1364人参与
# kpi面有什么特征 #
41693次浏览 331人参与
# vivo求职进展汇总 #
213748次浏览 1352人参与
# 你有哪些缓解焦虑的方法？ #
10664次浏览 288人参与
# 应届生应该先就业还是先择业 #
108510次浏览 629人参与
# 摸鱼打卡站 #
40815次浏览 696人参与
# 秋招被确诊为…… #
157998次浏览 715人参与
# 你觉得技术面多长时间合理？ #
95093次浏览 690人参与
# 打杂的实习你会去吗？ #
112207次浏览 974人参与
# 软开人，秋招你打算投哪些公司呢 #
97631次浏览 925人参与
# 秋招提前批启动你开冲了吗 #
119757次浏览 1908人参与
# 大家实习每天都在干啥 #
81443次浏览 500人参与