给你几个套娃,有长宽高和重量三个维度,如果后者每个维度都比前者大,就可以套进去,问最大的重量
时间: 2024-05-25 17:15:43 浏览: 130
俄罗斯套娃信封问题(两个维度都递增)1
假设有n个套娃,可以将它们按照重量从小到大排序。然后定义一个数组dp,其中dp[i]表示以第i个套娃为最外层套娃时,所能承受的最大重量。
对于第i个套娃,需要在前面的套娃中寻找可以套进去的套娃j(j<i),满足长宽高都小于第i个套娃,然后更新dp[i]=max(dp[i],dp[j]+weight[i]),其中weight[i]表示第i个套娃的重量。
最终的答案即为dp数组中的最大值。时间复杂度为O(n^2)。
阅读全文