2547. Minimum Cost to Split an Array Hard

1/**
2 * [2547] Minimum Cost to Split an Array
3 *
4 * You are given an integer array nums and an integer k.
5 * Split the array into some number of non-empty subarrays. The cost of a split is the sum of the importance value of each subarray in the split.
6 * Let trimmed(subarray) be the version of the subarray where all numbers which appear only once are removed.
7 * 
8 * 	For example, trimmed([3,1,2,4,3,4]) = [3,4,3,4].
9 * 
10 * The importance value of a subarray is k + trimmed(subarray).length.
11 * 
12 * 	For example, if a subarray is [1,2,3,3,3,4,4], then <font face="monospace">trimmed(</font>[1,2,3,3,3,4,4]) = [3,3,3,4,4].The importance value of this subarray will be k + 5.
13 * 
14 * Return the minimum possible cost of a split of nums.
15 * A subarray is a contiguous non-empty sequence of elements within an array.
16 *  
17 * <strong class="example">Example 1:
18 * 
19 * Input: nums = [1,2,1,2,1,3,3], k = 2
20 * Output: 8
21 * Explanation: We split nums to have two subarrays: [1,2], [1,2,1,3,3].
22 * The importance value of [1,2] is 2 + (0) = 2.
23 * The importance value of [1,2,1,3,3] is 2 + (2 + 2) = 6.
24 * The cost of the split is 2 + 6 = 8. It can be shown that this is the minimum possible cost among all the possible splits.
25 * 
26 * <strong class="example">Example 2:
27 * 
28 * Input: nums = [1,2,1,2,1], k = 2
29 * Output: 6
30 * Explanation: We split nums to have two subarrays: [1,2], [1,2,1].
31 * The importance value of [1,2] is 2 + (0) = 2.
32 * The importance value of [1,2,1] is 2 + (2) = 4.
33 * The cost of the split is 2 + 4 = 6. It can be shown that this is the minimum possible cost among all the possible splits.
34 * 
35 * <strong class="example">Example 3:
36 * 
37 * Input: nums = [1,2,1,2,1], k = 5
38 * Output: 10
39 * Explanation: We split nums to have one subarray: [1,2,1,2,1].
40 * The importance value of [1,2,1,2,1] is 5 + (3 + 2) = 10.
41 * The cost of the split is 10. It can be shown that this is the minimum possible cost among all the possible splits.
42 * 
43 *  
44 * Constraints:
45 * 
46 * 	1 <= nums.length <= 1000
47 * 	0 <= nums[i] < nums.length
48 * 	1 <= k <= 10^9
49 * 
50 *  
51 * <style type="text/css">.spoilerbutton {display:block; border:dashed; padding: 0px 0px; margin:10px 0px; font-size:150%; font-weight: bold; color:#000000; background-color:cyan; outline:0; 
52 * }
53 * .spoiler {overflow:hidden;}
54 * .spoiler > div {-webkit-transition: all 0s ease;-moz-transition: margin 0s ease;-o-transition: all 0s ease;transition: margin 0s ease;}
55 * .spoilerbutton[value="Show Message"] + .spoiler > div {margin-top:-500%;}
56 * .spoilerbutton[value="Hide Message"] + .spoiler {padding:5px;}
57 * </style>
58 * 
59 */
60pub struct Solution {}
61
62// problem: https://leetcode.com/problems/minimum-cost-to-split-an-array/
63// discuss: https://leetcode.com/problems/minimum-cost-to-split-an-array/discuss/?currentPage=1&orderBy=most_votes&query=
64
65// submission codes start here
66
67impl Solution {
68    pub fn min_cost(nums: Vec<i32>, k: i32) -> i32 {
69        0
70    }
71}
72
73// submission codes end
74
75#[cfg(test)]
76mod tests {
77    use super::*;
78
79    #[test]
80    fn test_2547() {
81    }
82}
83