深圳民治做网站常州免费网站建站模板

题目描述：

有一个 m x n 大小的矩形蛋糕，需要切成 1 x 1 的小块。

给你整数 m ，n 和两个数组：

• horizontalCut 的大小为 m - 1 ，其中 horizontalCut[i] 表示沿着水平线 i 切蛋糕的开销。
• verticalCut 的大小为 n - 1 ，其中 verticalCut[j] 表示沿着垂直线 j 切蛋糕的开销。

一次操作中，你可以选择任意不是 1 x 1 大小的矩形蛋糕并执行以下操作之一：

1. 沿着水平线 i 切开蛋糕，开销为 horizontalCut[i] 。
2. 沿着垂直线 j 切开蛋糕，开销为 verticalCut[j] 。

每次操作后，这块蛋糕都被切成两个独立的小蛋糕。

每次操作的开销都为最开始对应切割线的开销，并且不会改变。

请你返回将蛋糕全部切成 1 x 1 的蛋糕块的 最小 总开销。

代码思路：

1. 初始化结果：
   • 首先，将horizontalCut和verticalCut中所有切割位置的成本相加，得到初始的结果res。这表示仅仅进行所有给定的水平切割和垂直切割的成本总和。
2. 计算交叉切割的额外成本：
   • 接下来，代码通过两层嵌套循环遍历每一个水平切割位置hc和每一个垂直切割位置vc。
   • 对于每一对交叉的切割（即一个水平切割和一个垂直切割），它们会在矩形的某个位置相交。在这个相交点，选择水平切割成本hc和垂直切割成本vc中的较小值作为交叉切割的额外成本（因为交点只会被切割一次，无论两个方向的成本如何，实际发生的成本是两者中的较小值）。
   • 将这个较小值累加到res中。
3. 返回结果：
   • 最后，返回累加后的res，它代表了进行所有给定切割以及所有交叉切割所需的最小成本总和。

代码实现：

class Solution {
public:int minimumCost(int m, int n, vector<int> &horizontalCut, vector<int> &verticalCut) {int res = std::accumulate(horizontalCut.begin(), horizontalCut.end(), 0) +std::accumulate(verticalCut.begin(), verticalCut.end(), 0);for (const auto &hc: horizontalCut)for (const auto &vc: verticalCut)res += std::min({hc, vc});return res;}
};