给定
个单调不降的数组,初始计数器 。你需要进行 次操作,每次选择某个数组的第一个未被删除的元素 ,将 加上 ,然后将 从这个数组中删去。最大化 。
,所有数组长度之和不超过 ,值域 。
首先最多只有一个数组不是全选的,因为若存在两个数组
那么问题变成了扣掉一个物品的 01 背包,这个是经典问题,可以做到
时间复杂度是
Can't go up
给定
n 个单调不降的数组,初始计数器 sum=0。你需要进行 k 次操作,每次选择某个数组的第一个未被删除的元素 x,将 sum 加上 x,然后将 x 从这个数组中删去。最大化 sum。
1≤n,k≤3000,所有数组长度之和不超过 106,值域 [0,108]。
首先最多只有一个数组不是全选的,因为若存在两个数组
那么问题变成了扣掉一个物品的 01 背包,这个是经典问题,可以做到
时间复杂度是
扫码打赏,你说多少就多少