Fascinating Partitions
Time limit2.5sMemory limit1024 MB
For every k from 1 to N, compute the minimum and maximum total cost of splitting the array into exactly k contiguous subarrays, where a subarray costs its maximum element.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Divide and conquer, Stack, Array
- Solved
- No attempts yet
Problem
A subarray of an array is a contiguous portion of the array. A partition of an array into subarrays is a collection of subarrays that cover the whole array without overlaps, so each element of the array belongs to exactly one subarray. For example, if A = [3, 1, 4, 1, 5] is an array, [3, 1, 4] and [1, 5] form a partition of A into subarrays, while [3, 4, 5] is not a subarray of A.
Given an integer array and a partition of the array into non-empty subarrays, the cost of each subarray is its maximum element, and the cost of the whole partition is the sum of the costs of the subarrays.
As an example, consider the array [3, 5, 7, 1, 2, 4]. The partition formed by the subarrays [3, 5], [7], and [1, 2, 4] has cost 5 + 7 + 4 = 16, while the partition formed by the subarrays [3], [5, 7, 1], and [2, 4] has cost 3 + 7 + 4 = 14. Both partitions are formed by k = 3 subarrays, but they have different costs. Other partitions may have different costs.
Given an array A of N integers and an integer k such that 1 ≤ k ≤ N, consider the set P(A, k) containing all the partitions of A into k non-empty subarrays. Can you compute the minimum cost over P(A, k)? Can you also compute the maximum cost? For every possible k? Then go ahead.
Input
The first line contains an integer N (1 ≤ N ≤ 8000), the number of elements in the array A. The second line contains N integers A1, A2, . . . , AN (1 ≤ Ai ≤ 109 for i = 1, 2, . . . , N) representing the array.
Output
Output N lines. The k-th line contains two integers indicating respectively the minimum and maximum costs over P(A, k).