Partitioning an Array to Minimize the Sum of Maximums with a Weight Constraint
Разница между en1 и en2, 4 символ(ов) изменены
Hello Codeforces,↵

Is anyone familiar with this problem:↵

Consider an array of items with labels $1, \dots, n$ the $i$th of which has a weight $W_i$ and a cost $C_i$. The array must be partitioned into disjoint subarrays. The weight of a subarray from $i$ to $j$ is the sum $W_i + W_{i+1} + \dots + W_{j}$ and the cost is the maximum $\max(C_i, C_{i+1}, \dots, C_{j})$. No subarry in the partition can exceed a given maximum weight $W_\max$. Subject to this contraint, we wish to minimize the sum of subarray costs, i.e. the sum of maximums.↵

I have devised a solution that is $O(n \log n)$. I wonder if this is a well known problem and if a linear time solution exists. Also, are there any published results in the literature?↵

I am also curious about the extension of this problem to trees. Partition a tree into paths subject to 
the same constraints.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский AlwaysMerlin 2022-07-01 05:54:50 4 Tiny change: 'ubject to same cons' -> 'ubject to the same cons'
en1 Английский AlwaysMerlin 2022-07-01 05:54:16 935 Initial revision (published)