2025-03-03:切蛋糕的最小总开销Ⅱ。用go语言,你有一个大小为 m x n 的矩形蛋糕,需要将其切割成 1 x 1 的小块。给定两个整数 m 和 n 以及两个数组:
1.horizontalCut:长度为 m - 1,表示在每个水平切割线 i 切割蛋糕的成本。
2.verticalCut:长度为 n - 1,表示在每个垂直切割线 j 切割蛋糕的成本。
在每次操作中,你可以选择一块不是 1 x 1 大小的蛋糕,并执行下列操作之一:
1.沿着某个水平切割线 i 切割,费用为 horizontalCut[i]。
2.沿着某个垂直切割线 j 切割,费用为 verticalCut[j]。
每次操作都会将蛋糕切割成两个独立的小部分,而每个切割的费用是固定的,不会改变。请你返回将蛋糕完全切分为 1 x 1 小块的最小总开销。
1 <= m, n <= 100000。
horizontalCut.length == m - 1。
verticalCut.length == n - 1。
1 <= horizontalCut[i], verticalCut[i] <= 1000。
输入:m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]。
输出:13。
解释:
沿着垂直线 0 切开蛋糕,开销为 5 。
沿着水平线 0 切开 3 x 1 的蛋糕块,开销为 1 。
沿着水平线 0 切开 3 x 1 的蛋糕块,开销为 1 。
沿着水平线 1 切开 2 x 1 的蛋糕块,开销为 3 。
沿着水平线 1 切开 2 x 1 的蛋糕块,开销为 3 。
总开销为 5 + 1 + 1 + 3 + 3 = 13 。
相似问题