卖木头块

2312. 卖木头块

给你两个整数 m 和 n ，分别表示一块矩形木块的高和宽。同时给你一个二维整数数组 prices ，其中 prices[i] = [h_i, w_i, price_i] 表示你可以以 price_i 元的价格卖一块高为 h_i 宽为 w_i 的矩形木块。

每一次操作中，你必须按下述方式之一执行切割操作，以得到两块更小的矩形木块：

沿垂直方向按高度完全切割木块，或
沿水平方向按宽度完全切割木块

在将一块木块切成若干小木块后，你可以根据 prices 卖木块。你可以卖多块同样尺寸的木块。你不需要将所有小木块都卖出去。你不能旋转切好后木块的高和宽。

请你返回切割一块大小为 m x n 的木块后，能得到的最多钱数。

注意你可以切割木块任意次。

示例 1：

输入：m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]]
输出：19
解释：上图展示了一个可行的方案。包括：
- 2 块 2 x 2 的小木块，售出 2 * 7 = 14 元。
- 1 块 2 x 1 的小木块，售出 1 * 3 = 3 元。
- 1 块 1 x 4 的小木块，售出 1 * 2 = 2 元。
总共售出 14 + 3 + 2 = 19 元。
19 元是最多能得到的钱数。

示例 2：

输入：m = 4, n = 6, prices = [[3,2,10],[1,4,2],[4,1,3]]
输出：32
解释：上图展示了一个可行的方案。包括：
- 3 块 3 x 2 的小木块，售出 3 * 10 = 30 元。
- 1 块 1 x 4 的小木块，售出 1 * 2 = 2 元。
总共售出 30 + 2 = 32 元。
32 元是最多能得到的钱数。
注意我们不能旋转 1 x 4 的木块来得到 4 x 1 的木块。

提示：

1 <= m, n <= 200
1 <= prices.length <= 2 * 10⁴
prices[i].length == 3
1 <= h_i <= m
1 <= w_i <= n
1 <= price_i <= 10⁶
所有 (h_i, w_i) 互不相同 。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: long long sellingWood(int m, int n, vector<vector<int>>& prices) { } };

php 解法, 执行用时: 657 ms, 内存消耗: 31.3 MB, 提交时间: 2024-03-15 10:26:25

class Solution {

    /**
     * @param Integer $m
     * @param Integer $n
     * @param Integer[][] $prices
     * @return Integer
     */
    function sellingWood($m, $n, $prices) {
        $f = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
        
        foreach ($prices as $price) {
            list($h, $w, $p) = $price;
            $f[$h][$w] = $p;
        }
        
        for ($i = 1; $i <= $m; $i++) {
            for ($j = 1; $j <= $n; $j++) {
                $verticalCut = 0;
                $horizontalCut = 0;
                
                for ($k = 1; $k <= $j / 2; $k++) {
                    $verticalCut = max($verticalCut, $f[$i][$k] + $f[$i][$j - $k]);
                }
                
                for ($k = 1; $k <= $i / 2; $k++) {
                    $horizontalCut = max($horizontalCut, $f[$k][$j] + $f[$i - $k][$j]);
                }
                
                $f[$i][$j] = max($f[$i][$j], max($verticalCut, $horizontalCut));
            }
        }
        
        return $f[$m][$n];
    }
}

golang 解法, 执行用时: 60 ms, 内存消耗: 7.2 MB, 提交时间: 2023-10-12 10:15:10

func sellingWood1(m, n int, prices [][]int) int64 {
	pr := make([][]int, m+1)
	for i := range pr {
		pr[i] = make([]int, n+1)
	}
	for _, price := range prices {
		pr[price[0]][price[1]] = price[2]
	}

	f := make([][]int64, m+1)
	for i := 1; i <= m; i++ {
		f[i] = make([]int64, n+1)
		for j := 1; j <= n; j++ {
			f[i][j] = int64(pr[i][j])
			for k := 1; k < j; k++ { // 垂直切割
				f[i][j] = max(f[i][j], f[i][k]+f[i][j-k])
			}
			for k := 1; k < i; k++ { // 水平切割
				f[i][j] = max(f[i][j], f[k][j]+f[i-k][j])
			}
		}
	}
	return f[m][n]
}

// 优化
func sellingWood(m, n int, prices [][]int) int64 {
	f := make([][]int64, m+1)
	for i := range f {
		f[i] = make([]int64, n+1)
	}
	for _, price := range prices {
		f[price[0]][price[1]] = int64(price[2])
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			for k := 1; k <= j/2; k++ { // 垂直切割
				f[i][j] = max(f[i][j], f[i][k]+f[i][j-k])
			}
			for k := 1; k <= i/2; k++ { // 水平切割
				f[i][j] = max(f[i][j], f[k][j]+f[i-k][j])
			}
		}
	}
	return f[m][n]
}

func max(a, b int64) int64 { if b > a { return b }; return a }

java 解法, 执行用时: 32 ms, 内存消耗: 48.2 MB, 提交时间: 2023-10-12 10:14:08

class Solution {
    public long sellingWood1(int m, int n, int[][] prices) {
        var pr = new int[m + 1][n + 1];
        for (var p : prices) pr[p[0]][p[1]] = p[2];

        var f = new long[m + 1][n + 1];
        for (var i = 1; i <= m; i++)
            for (var j = 1; j <= n; j++) {
                f[i][j] = pr[i][j];
                for (var k = 1; k < j; k++) f[i][j] = Math.max(f[i][j], f[i][k] + f[i][j - k]); // 垂直切割
                for (var k = 1; k < i; k++) f[i][j] = Math.max(f[i][j], f[k][j] + f[i - k][j]); // 水平切割
            }
        return f[m][n];
    }

    // 优化
    public long sellingWood(int m, int n, int[][] prices) {
        var f = new long[m + 1][n + 1];
        for (var p : prices) f[p[0]][p[1]] = p[2];
        for (var i = 1; i <= m; i++)
            for (var j = 1; j <= n; j++) {
                for (var k = 1; k <= j / 2; k++) f[i][j] = Math.max(f[i][j], f[i][k] + f[i][j - k]); // 垂直切割
                for (var k = 1; k <= i / 2; k++) f[i][j] = Math.max(f[i][j], f[k][j] + f[i - k][j]); // 水平切割
            }
        return f[m][n];
    }
}

cpp 解法, 执行用时: 112 ms, 内存消耗: 24.9 MB, 提交时间: 2023-10-12 10:12:46

class Solution {
public:
    long long sellingWood1(int m, int n, vector<vector<int>> &prices) {
        int pr[m + 1][n + 1]; memset(pr, 0, sizeof(pr));
        for (auto &p : prices) pr[p[0]][p[1]] = p[2];

        long f[m + 1][n + 1];
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++) {
                f[i][j] = pr[i][j];
                for (int k = 1; k < j; k++) f[i][j] = max(f[i][j], f[i][k] + f[i][j - k]); // 垂直切割
                for (int k = 1; k < i; k++) f[i][j] = max(f[i][j], f[k][j] + f[i - k][j]); // 水平切割
            }
        return f[m][n];
    }

    // 优化
    long long sellingWood(int m, int n, vector<vector<int>> &prices) {
        long f[m + 1][n + 1]; memset(f, 0, sizeof(f));
        for (auto &p : prices) f[p[0]][p[1]] = p[2];
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= j / 2; k++) f[i][j] = max(f[i][j], f[i][k] + f[i][j - k]); // 垂直切割
                for (int k = 1; k <= i / 2; k++) f[i][j] = max(f[i][j], f[k][j] + f[i - k][j]); // 水平切割
            }
        return f[m][n];
    }
};

python3 解法, 执行用时: 1412 ms, 内存消耗: 21.9 MB, 提交时间: 2023-10-12 10:10:56

'''
f[i][j] 表示高度为i,宽度为j的木块售卖能获得的最多收益
状态转移，三种情况，直接售卖，垂直切割，水平切割，取最大
f[i][j] = max(直接售卖，f[i][k] + f[i][j-k], f[k][j] + f[i-k][j])
'''
class Solution:
    def sellingWood1(self, m: int, n: int, prices: List[List[int]]) -> int:
        pr = {(h, w): p for h, w, p in prices}
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                f[i][j] = max(pr.get((i, j), 0),
                              max((f[i][k] + f[i][j - k] for k in range(1, j)), default=0),  # 垂直切割
                              max((f[k][j] + f[i - k][j] for k in range(1, i)), default=0))  # 水平切割
        return f[m][n]
        
        
    '''
    优化两点，内层循环到一半即可；从小到大计算f，那么prices直接记录到f里不影响
    '''
    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for h, w, p in prices:
            f[h][w] = p
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                f[i][j] = max(f[i][j],
                              max((f[i][k] + f[i][j - k] for k in range(1, j // 2 + 1)), default=0),  # 垂直切割
                              max((f[k][j] + f[i - k][j] for k in range(1, i // 2 + 1)), default=0))  # 水平切割
        return f[m][n]

上一题

下一题

详情