swott
2019-07-28 20:28 算法工程师
关注
不是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
相关推荐
点赞 评论 收藏
分享
06-14 13:52
广西民族大学 电子信息类 点赞 评论 收藏
分享
06-12 18:41
查看13道真题和解析 点赞 评论 收藏
分享
牛客热帖
正在热议
# 牛客帮帮团来啦！有问必答 #
1326658次浏览 18666人参与
# 非技术岗薪资爆料 #
53175次浏览 730人参与
# 极具前瞻性，现代汽车编程题 #
9393次浏览 186人参与
# 和牛牛一起刷题打卡 #
44486次浏览 3572人参与
# 写简历别走弯路 #
360069次浏览 4535人参与
# 我发现了面试通关密码 #
409165次浏览 7308人参与
# 不去互联网可以去金融科技 #
47436次浏览 507人参与
# 产品每日一题 #
1629次浏览 93人参与
# 来聊聊你目前的求职进展 #
229738次浏览 2905人参与
# 华子oc时间线 #
11171次浏览 60人参与
# 投递实习岗位前的准备 #
753233次浏览 13143人参与
# 如果可以选，你最想从事什么工作 #
219637次浏览 3399人参与
# 晒一晒我的offer #
4029528次浏览 60392人参与
# 国企vs私企，你更想去？ #
34467次浏览 401人参与
# 我想象的工作vs实际工作 #
116709次浏览 1807人参与
# 软件开发2024笔面经 #
1570098次浏览 36084人参与
# 硬件兄弟们 甩出你的华为奖状 #
37879次浏览 224人参与
# 24届软开秋招面试经验大赏 #
1238575次浏览 18675人参与
# 互联网公司评价 #
105667次浏览 1371人参与
# 参加过提前批的机械人，你们还参加秋招么 #
16595次浏览 382人参与
# 百度工作体验 #
31881次浏览 315人参与
# 机械制造笔面经 #
11403次浏览 331人参与