某个工厂收到了一块矩形形状的巨型紫晶矿石,其长宽6m x 4m(横着的为长,竖着的为宽),现在需要将其切割为24块1m x 1m的小型紫晶矿石,所以工程师现在大理石上划了5条垂直方向的竖线,3条水平方向的横线(俯视),但是因为紫晶矿石每处的厚度不同,所以沿着某条竖线或横线切割的成本不同。若切割后紫晶矿石被一分为二,因为其体积巨大,我们无法将其再拼接起让第二刀直接切为4块,只能分别对分开的块各自再切割一刀,现在工程师告诉你5条竖线单块切割的代价分别是(12,15,5,20,9),3条横线单块切割的代价为(4,13,16),则将巨型紫晶矿石切割为24块1m*1m的小型紫晶矿石所需要的最小代价为多少
时间: 2024-04-22 22:28:16 浏览: 165
为了找到将巨型紫晶矿石切割为24块1m x 1m的小型紫晶矿石的最小代价,我们可以使用动态规划的方法来解决这个问题。
我们可以定义一个二维数组dp,其中dp[i][j]表示将前i条竖线和前j条横线的区域切割为24块小型紫晶矿石所需要的最小代价。
首先,我们可以初始化dp数组的第一行和第一列。对于第一行和第一列,dp[0][j]和dp[i][0]分别表示只有横线或竖线时的切割代价。根据题目,我们可以得到:
dp[0][0] = 0
dp[0][1] = 4
dp[0][2] = 4 + 13
dp[0][3] = 4 + 13 + 16
dp[1][0] = 12
dp[2][0] = 12 + 15
dp[3][0] = 12 + 15 + 5
dp[4][0] = 12 + 15 + 5 + 20
dp[5][0] = 12 + 15 + 5 + 20 + 9
接下来,我们可以使用动态规划的思想来填充dp数组。对于每个位置(i, j),我们可以考虑两种情况:
1. 如果我们选择在第i条竖线切割,则可以将区域分为两部分:左边是从第1条竖线到第i-1条竖线的区域,右边是从第i+1条竖线到最后一条竖线的区域。我们可以计算出左右两部分的代价之和,并加上第i条竖线的切割代价。
2. 如果我们选择在第j条横线切割,则可以将区域分为两部分:上面是从第1条横线到第j-1条横线的区域,下面是从第j+1条横线到最后一条横线的区域。同样地,我们可以计算出上下两部分的代价之和,并加上第j条横线的切割代价。
我们需要选择上述两种情况中的最小代价作为dp[i][j]的值。最终,dp[5][3]即为将巨型紫晶矿石切割为24块小型紫晶矿石所需要的最小代价。
综上所述,我们可以使用动态规划来解决该问题,最终计算出dp[5][3]即为所需的最小代价。
阅读全文