关注
不是dl,只ac10%,说一个思路,抛砖引玉,首先根据长度对积木排序,积木的长度和重量是绑定的,排序的话,注意不要改变其对应关系,python实现很简单,长度重量绑定成元组,然后对长度排序。用动态规划,lengths[i]表示[0, i]区间内最高的金字塔,weights[i]表示其对应重量,对于每一个i遍历j,j<i, 如果W[i] * 7 >= weights[i], lengths[i] = max(lengths[j] + 1, lengths[i]), 时间复杂度O(n^2)。当时没有做判断的一点是如果lengths[j] + 1 == lengths[i],应该要比较weights[j] + W[i]与当前weights[i]的大小,若小则更新。还有一点关于输入的疑问,会不会存在长度相同但重量不同的积木,如果有,想先做去重,只保留重量最轻的。
查看原帖
点赞 6
相关推荐
07-02 13:36
门头沟学院 Java 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 大家每天通勤多久? #
45807次浏览 345人参与
# 银行笔面经互助 #
134088次浏览 1166人参与
# 现代汽车前瞻技术研发急速编程挑战赛 #
32723次浏览 257人参与
# 上班到公司第一件事做什么? #
58399次浏览 498人参与
# 设计人如何选offer #
119112次浏览 740人参与
# CVTE求职进展汇总 #
16337次浏览 292人参与
# 上班苦还是上学苦呢? #
229579次浏览 1357人参与
# 非技术投递记录 #
604357次浏览 6402人参与
# 90后北漂现状 #
24865次浏览 201人参与
# 百度工作体验 #
226712次浏览 1995人参与
# 机械人与华为的爱恨情仇 #
117810次浏览 951人参与
# 金融财会交流会 #
110499次浏览 380人参与
# 工作中,努力重要还是选择重要? #
136845次浏览 1681人参与
# 发工资后,你做的第一件事是什么 #
68700次浏览 232人参与
# 机械人,你的秋招第一份简历被谁挂了 #
141634次浏览 1982人参与
# Offer比较,你最看重什么? #
186917次浏览 1287人参与
# 工作中哪个瞬间让你想离职 #
26394次浏览 179人参与
# 你觉得实习能学到东西吗 #
40417次浏览 776人参与
# 秋招什么时候开投比较合适? #
28545次浏览 351人参与
# 联想求职进展汇总 #
270982次浏览 2053人参与
# 机械人集合!你是什么工程师? #
16345次浏览 89人参与