3500. Minimum Cost to Divide Array Into Subarrays Hard

1/**
2 * [3500] Minimum Cost to Divide Array Into Subarrays
3 *
4 * You are given two integer arrays, nums and cost, of the same size, and an integer k.
5 * You can divide nums into <span data-keyword="subarray-nonempty">subarrays</span>. The cost of the i^th subarray consisting of elements nums[l..r] is:
6 * 
7 * 	(nums[0] + nums[1] + ... + nums[r] + k * i) * (cost[l] + cost[l + 1] + ... + cost[r]).
8 * 
9 * Note that i represents the order of the subarray: 1 for the first subarray, 2 for the second, and so on.
10 * Return the minimum total cost possible from any valid division.
11 *  
12 * <strong class="example">Example 1:
13 * <div class="example-block">
14 * Input: <span class="example-io">nums = [3,1,4], cost = [4,6,6], k = 1</span>
15 * Output: <span class="example-io">110</span>
16 * Explanation:
17 * The minimum total cost possible can be achieved by dividing nums into subarrays [3, 1] and [4].
18 * 
19 * 	The cost of the first subarray [3,1] is (3 + 1 + 1 * 1) * (4 + 6) = 50.
20 * 	The cost of the second subarray [4] is (3 + 1 + 4 + 1 * 2) * 6 = 60.
21 * </div>
22 * <strong class="example">Example 2:
23 * <div class="example-block">
24 * Input: <span class="example-io">nums = [4,8,5,1,14,2,2,12,1], cost = [7,2,8,4,2,2,1,1,2], k = 7</span>
25 * Output: 985
26 * Explanation:
27 * The minimum total cost possible can be achieved by dividing nums into subarrays [4, 8, 5, 1], [14, 2, 2], and [12, 1].
28 * 
29 * 	The cost of the first subarray [4, 8, 5, 1] is (4 + 8 + 5 + 1 + 7 * 1) * (7 + 2 + 8 + 4) = 525.
30 * 	The cost of the second subarray [14, 2, 2] is (4 + 8 + 5 + 1 + 14 + 2 + 2 + 7 * 2) * (2 + 2 + 1) = 250.
31 * 	The cost of the third subarray [12, 1] is (4 + 8 + 5 + 1 + 14 + 2 + 2 + 12 + 1 + 7 * 3) * (1 + 2) = 210.
32 * </div>
33 *  
34 * Constraints:
35 * 
36 * 	1 <= nums.length <= 1000
37 * 	cost.length == nums.length
38 * 	1 <= nums[i], cost[i] <= 1000
39 * 	1 <= k <= 1000
40 * 
41 */
42pub struct Solution {}
43
44// problem: https://leetcode.com/problems/minimum-cost-to-divide-array-into-subarrays/
45// discuss: https://leetcode.com/problems/minimum-cost-to-divide-array-into-subarrays/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48
49impl Solution {
50    pub fn minimum_cost(nums: Vec<i32>, cost: Vec<i32>, k: i32) -> i64 {
51        
52    }
53}
54
55// submission codes end
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn test_3500() {
63    }
64}
65