text: Minimum Cost to cut a board into squares | C ++ program to divide a board into m * n squares ; method returns minimum cost to break board into m * n squares ; sort the horizontal cost in reverse order ; sort the vertical cost in reverse order ; initialize current width as 1 ; loop until one or both cost array are processed ; increase current horizontal part count by 1 ; increase current vertical part count by 1 ; loop for horizontal array , if remains ; loop for vertical array , if remains ; Driver code to test above methods
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int minimumCostOfBreaking ( int X [ ] , int Y [ ] , int m , int n ) { int res = 0 ; sort ( X , X + m , greater < int > ( ) ) ; sort ( Y , Y + n , greater < int > ( ) ) ; int hzntl = 1 , vert = 1 ; int i = 0 , j = 0 ; while ( i < m && j < n ) { if ( X [ i ] > Y [ j ] ) { res += X [ i ] * vert ; hzntl ++ ; i ++ ; } else { res += Y [ j ] * hzntl ; vert ++ ; j ++ ; } } int total = 0 ; while ( i < m ) total += X [ i ++ ] ; res += total * vert ; total = 0 ; while ( j < n ) total += Y [ j ++ ] ; res += total * hzntl ; return res ; } int main ( ) { int m = 6 , n = 4 ; int X [ m - 1 ] = { 2 , 1 , 3 , 1 , 4 } ; int Y [ n - 1 ] = { 4 , 1 , 2 } ; cout << minimumCostOfBreaking ( X , Y , m - 1 , n - 1 ) ; return 0 ; }