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.

#### History

Revisions Rev. Lang. By When Δ Comment
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)