Divide chocolate bar into pieces , minimizing the area of invalid pieces | C ++ program for the above approach ; Store valid dimensions ; Stores memoization ; Utility function to calculate minimum invalid area for Chocolate piece having dimension ( l , r ) ; Check whether current piece is valid or not If it is , then return zero for current dimension ; Making all possible horizontal cuts , one by one and calculating the sum of minimum invalid area for both the resulting pieces ; Making all possible vertical cuts , one by one and calculating the sum of minimum invalid area for both the resulting pieces ; Store the computed result ; Function to calculate minimum invalid area for Chocolate piece having dimension ( l , r ) ; Total number of valid dimensions ; Storing valid dimensions as for every ( x , y ) both ( x , y ) and ( y , x ) are valid ; Fill dp [ ] [ ] table with - 1 , indicating that results are not computed yet ; Stores minimum area ; Print minArea as the output ; Driver Code ; Given N & M ; Given valid dimensions ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int sz = 1001 ; bool ok [ sz ] [ sz ] = { } ; int dp [ sz ] [ sz ] ; int minInvalidAreaUtil ( int l , int b ) { if ( dp [ l ] [ b ] == -1 ) { if ( ok [ l ] [ b ] ) { return dp [ l ] [ b ] = 0 ; } int ans = l * b ; for ( int i = 1 ; i < b ; i ++ ) { ans = min ( ans , minInvalidAreaUtil ( l , i ) + minInvalidAreaUtil ( l , b - i ) ) ; } for ( int i = 1 ; i < l ; i ++ ) { ans = min ( ans , minInvalidAreaUtil ( i , b ) + minInvalidAreaUtil ( l - i , b ) ) ; } dp [ l ] [ b ] = ans ; } return dp [ l ] [ b ] ; } void minInvalidArea ( int N , int M , vector < pair < int , int > > & dimensions ) { int K = dimensions . size ( ) ; for ( int i = 0 ; i < K ; i ++ ) { ok [ dimensions [ i ] . first ] [ dimensions [ i ] . second ] = 1 ; ok [ dimensions [ i ] . second ] [ dimensions [ i ] . first ] = 1 ; } for ( int i = 0 ; i < sz ; i ++ ) { for ( int j = 0 ; j < sz ; j ++ ) { dp [ i ] [ j ] = -1 ; } } int minArea = minInvalidAreaUtil ( N , M ) ; cout << minArea << endl ; } int main ( ) { int N = 10 , M = 10 ; vector < pair < int , int > > dimensions = { { 3 , 5 } } ; minInvalidArea ( N , M , dimensions ) ; return 0 ; }