网站按钮特效,搜索引擎关键词怎么优化,广州百度seo优化排名,集团企业网站建设题目描述#xff1a;
有一个 m x n 大小的矩形蛋糕#xff0c;需要切成 1 x 1 的小块。
给你整数 m #xff0c;n 和两个数组#xff1a;
horizontalCut 的大小为 m - 1 #xff0c;其中 horizontalCut[i] 表示沿着水平线 i 切蛋糕的开销。verticalCut 的大小为 n - 1 …题目描述
有一个 m x n 大小的矩形蛋糕需要切成 1 x 1 的小块。
给你整数 m n 和两个数组
horizontalCut 的大小为 m - 1 其中 horizontalCut[i] 表示沿着水平线 i 切蛋糕的开销。verticalCut 的大小为 n - 1 其中 verticalCut[j] 表示沿着垂直线 j 切蛋糕的开销。
一次操作中你可以选择任意不是 1 x 1 大小的矩形蛋糕并执行以下操作之一
沿着水平线 i 切开蛋糕开销为 horizontalCut[i] 。沿着垂直线 j 切开蛋糕开销为 verticalCut[j] 。
每次操作后这块蛋糕都被切成两个独立的小蛋糕。
每次操作的开销都为最开始对应切割线的开销并且不会改变。
请你返回将蛋糕全部切成 1 x 1 的蛋糕块的 最小 总开销。
代码思路
初始化结果 首先将horizontalCut和verticalCut中所有切割位置的成本相加得到初始的结果res。这表示仅仅进行所有给定的水平切割和垂直切割的成本总和。计算交叉切割的额外成本 接下来代码通过两层嵌套循环遍历每一个水平切割位置hc和每一个垂直切割位置vc。对于每一对交叉的切割即一个水平切割和一个垂直切割它们会在矩形的某个位置相交。在这个相交点选择水平切割成本hc和垂直切割成本vc中的较小值作为交叉切割的额外成本因为交点只会被切割一次无论两个方向的成本如何实际发生的成本是两者中的较小值。将这个较小值累加到res中。返回结果 最后返回累加后的res它代表了进行所有给定切割以及所有交叉切割所需的最小成本总和。
代码实现
class Solution {
public:int minimumCost(int m, int n, vectorint horizontalCut, vectorint 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;}
};
