Split array into subarrays at minimum cost by minimizing count of repeating elements in each subarray | C ++ program for the above approach ; Function to find the minimum cost of splitting the array into subarrays ; Size of the array ; Get the maximum element ; dp [ ] will store the minimum cost upto index i ; Initialize the result array ; Initialise the first element ; Create the frequency array ; Update the frequency ; Counting the cost of the duplicate element ; Minimum cost of operation from 0 to j ; Total cost of the array ; Driver Code ; Given cost K ; Function Call
#include <bits/stdc++.h> NEW_LINE #define ll  long long NEW_LINE using namespace std ; int findMinCost ( vector < int > & a , int k ) { int n = ( int ) a . size ( ) ; int max_ele = * max_element ( a . begin ( ) , a . end ( ) ) ; ll dp [ n + 1 ] ; for ( int i = 1 ; i <= n ; ++ i ) dp [ i ] = INT_MAX ; dp [ 0 ] = 0 ; for ( int i = 0 ; i < n ; ++ i ) { int freq [ max_ele + 1 ] ; memset ( freq , 0 , sizeof freq ) ; for ( int j = i ; j < n ; ++ j ) { freq [ a [ j ] ] ++ ; int cost = 0 ; for ( int x = 0 ; x <= max_ele ; ++ x ) { cost += ( freq [ x ] == 1 ) ? 0 : freq [ x ] ; } dp [ j + 1 ] = min ( dp [ i ] + cost + k , dp [ j + 1 ] ) ; } } return dp [ n ] ; } int main ( ) { vector < int > arr = { 1 , 2 , 1 , 1 , 1 } ; int K = 2 ; cout << findMinCost ( arr , K ) ; return 0 ; }