Partitioning an Array to Minimize the Sum of Maximums with a Weight Constraint

Revision en2, by AlwaysMerlin, 2022-07-01 05:54:50

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. Lang. By When Δ Comment
en2 English AlwaysMerlin 2022-07-01 05:54:50 4 Tiny change: 'ubject to same cons' -> 'ubject to the same cons'
en1 English AlwaysMerlin 2022-07-01 05:54:16 935 Initial revision (published)