Minimize cost to empty given array where cost of removing an element is its absolute difference with Time instant | C ++ program for the above approach ; Function to find the minimum cost to delete all array elements ; Sort the input array ; Store the maximum time to delete the array in the worst case ; Store the result in cost [ ] [ ] table ; Initialize the table cost [ ] [ ] ; Base Case ; Store the minimum of all cost values of the previous index ; Iterate from range [ 1 , n ] using variable i ; Update prev ; Iterate from range [ 1 , m ] using variable j ; Update cost [ i ] [ j ] ; Update the prev ; Store the minimum cost to delete all elements ; Find the minimum of all values of cost [ n ] [ j ] ; Print minimum cost ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define INF  10000 NEW_LINE void minCost ( int arr [ ] , int n ) { sort ( arr , arr + n ) ; int m = 2 * n ; int cost [ n + 1 ] [ m + 1 ] ; for ( int i = 0 ; i <= n ; i ++ ) { for ( int j = 0 ; j <= m ; j ++ ) { cost [ i ] [ j ] = INF ; } } cost [ 0 ] [ 0 ] = 0 ; int prev = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { prev = cost [ i - 1 ] [ 0 ] ; for ( int j = 1 ; j <= m ; j ++ ) { cost [ i ] [ j ] = min ( cost [ i ] [ j ] , prev + abs ( j - arr [ i - 1 ] ) ) ; prev = min ( prev , cost [ i - 1 ] [ j ] ) ; } } int minCost = INF ; for ( int j = 1 ; j <= m ; j ++ ) { minCost = min ( minCost , cost [ n ] [ j ] ) ; } cout << minCost ; } int main ( ) { int arr [ ] = { 4 , 2 , 4 , 4 , 5 , 2 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; minCost ( arr , N ) ; return 0 ; }