mediumArrayDynamic ProgrammingGreedySorting 0 views

Minimum Cost for Cutting Cake I

There is an m x n cake that needs to be cut into 1 x 1 pieces.

There is an m x n cake that needs to be cut into 1 x 1 pieces.

You are given integers m, n, and two arrays:

In one operation, you can choose any piece of cake that is not yet a 1 x 1 square and perform one of the following cuts:

After the cut, the piece of cake is divided into two distinct pieces.

The cost of a cut depends only on the initial cost of the line and does not change.

Return the minimum total cost to cut the entire cake into 1 x 1 pieces.

Example 1

Input: m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]

Output: 13

Explanation: The total cost is 5 + 1 + 1 + 3 + 3 = 13 .

Example 2

Input: m = 2, n = 2, horizontalCut = [7], verticalCut = [4]

Output: 15

Explanation: The total cost is 7 + 4 + 4 = 15 .

Constraints

  • 1 <= m, n <= 20
  • horizontalCut.length == m - 1
  • verticalCut.length == n - 1
  • 1 <= horizontalCut[i], verticalCut[i] <= 10^3

Hints

Companies

No companies reported yet.

Discussion

Sign in to join the discussion.

Loading discussion...

Test results

No test cases yet.