#2312
Selling Pieces of Wood
candidate master · 1350 · lc hard +32 · verified · 52.8% accepted · 578 likes · top 43%
Description
You are given two integers m and n (height and width) of a rectangular piece of wood, and a 2D array prices where prices[i] = [hi, wi, pricei] means a piece of height hi and width wi can be sold for pricei dollars.
You may make any number of complete vertical or horizontal cuts to divide the wood, then sell the resulting pieces at their listed prices (the same dimensions may be sold multiple times). Wood grain is direction-sensitive, so pieces cannot be rotated.
Return the maximum revenue obtainable from the m x n piece.
Example 1:
Input: m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]]
Output: 19
Explanation: The diagram above shows a possible scenario. It consists of:
- 2 pieces of wood shaped 2 x 2, selling for a price of 2 * 7 = 14.
- 1 piece of wood shaped 2 x 1, selling for a price of 1 * 3 = 3.
- 1 piece of wood shaped 1 x 4, selling for a price of 1 * 2 = 2.
This obtains a total of 14 + 3 + 2 = 19 money earned.
It can be shown that 19 is the maximum amount of money that can be earned.
Example 2:
Input: m = 4, n = 6, prices = [[3,2,10],[1,4,2],[4,1,3]]
Output: 32
Explanation: The diagram above shows a possible scenario. It consists of:
- 3 pieces of wood shaped 3 x 2, selling for a price of 3 * 10 = 30.
- 1 piece of wood shaped 1 x 4, selling for a price of 1 * 2 = 2.
This obtains a total of 30 + 2 = 32 money earned.
It can be shown that 32 is the maximum amount of money that can be earned.
Notice that we cannot rotate the 1 x 4 piece of wood to obtain a 4 x 1 piece of wood.
Code
1
2
3