不是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-06 21:28
点赞 评论 收藏
分享
牛客网
牛客企业服务