某个工厂收到了一块矩形形状的巨型紫晶矿石,其长宽6mx4m,现在需要将其切割为24块1mx1m的小型紫晶矿石(横着的为长,竖着的为宽),所以工程师现在大理石上划了5条垂直方向的竖线,3条水平方向的横线(俯视),但是因为紫晶矿石每处的厚度不同,所以沿着某条竖线或横线切割的成本不同。若切割后紫晶矿石被一分为二,因为其体积巨大,我们无法将其再拼接起让第二刀直接且为4块,只能分别对分开的块各自再切割一刀,现在工程师告诉你5条竖线单块切割的代价分别是(12,15,5,20,9),3条横线单块切割的代价为(4,13,16),则将巨型紫晶矿石切割为24块1m*1m的小型紫晶矿石所需要的代价为多少
时间: 2024-04-22 11:28:15 浏览: 90
矩形切割,用的是递归算法。
5星 · 资源好评率100%
根据题目描述,我们需要将6m*4m的矩形巨型紫晶矿石切割为24块1m*1m的小型紫晶矿石。切割的代价取决于沿着竖线和横线的切割次数以及每次切割的代价。
首先,我们需要计算竖线切割的代价。根据题目,有5条竖线,分别是12、15、5、20、9的代价。我们可以根据每个切割点左侧和右侧的代价总和,并选择代价最小的切割点进行切割。
第一条竖线切割点左侧的代价总和为0,右侧的代价总和为15+5+20+9=49。
第二条竖线切割点左侧的代价总和为12,右侧的代价总和为5+20+9=34。
第三条竖线切割点左侧的代价总和为12+15=27,右侧的代价总和为20+9=29。
第四条竖线切割点左侧的代价总和为12+15+5=32,右侧的代价总和为9。
第五条竖线切割点左侧的代价总和为12+15+5+20=52,右侧的代价总和为0。
所以,选择第一条竖线进行切割,代价为0。
接下来,我们计算横线切割的代价。根据题目,有3条横线,分别是4、13、16的代价。同样地,我们计算每个切割点上方和下方的代价总和,并选择代价最小的切割点进行切割。
第一条横线切割点上方的代价总和为0,下方的代价总和为13+16=29。
第二条横线切割点上方的代价总和为4,下方的代价总和为16。
第三条横线切割点上方的代价总和为4+13=17,下方的代价总和为0。
所以,选择第三条横线进行切割,代价为17。
最终,紫晶矿石切割的总代价为0+17=17。
阅读全文