关注
不是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
相关推荐
牛客热帖
正在热议
# 牛客帮帮团来啦!有问必答 #
1328237次浏览 18671人参与
# 非技术岗薪资爆料 #
53416次浏览 730人参与
# 极具前瞻性,现代汽车编程题 #
9508次浏览 188人参与
# 和牛牛一起刷题打卡 #
44930次浏览 3575人参与
# 写简历别走弯路 #
360285次浏览 4535人参与
# 我发现了面试通关密码 #
409502次浏览 7309人参与
# OPPO开奖 #
59081次浏览 852人参与
# 产品每日一题 #
1762次浏览 93人参与
# 来聊聊你目前的求职进展 #
229962次浏览 2905人参与
# 华子oc时间线 #
11276次浏览 60人参与
# 投递实习岗位前的准备 #
753600次浏览 13146人参与
# 如果可以选,你最想从事什么工作 #
219966次浏览 3401人参与
# 晒一晒我的offer #
4031712次浏览 60399人参与
# 国企vs私企,你更想去? #
34608次浏览 404人参与
# 我想象的工作vs实际工作 #
116893次浏览 1807人参与
# 软件开发2024笔面经 #
1570656次浏览 36086人参与
# 硬件兄弟们 甩出你的华为奖状 #
37964次浏览 224人参与
# 24届软开秋招面试经验大赏 #
1239173次浏览 18675人参与
# 互联网公司评价 #
105862次浏览 1371人参与
# 参加过提前批的机械人,你们还参加秋招么 #
16720次浏览 382人参与
# 百度工作体验 #
31991次浏览 315人参与
# 机械制造笔面经 #
11772次浏览 332人参与