最小成本切割木板

Question

给定一个由M×N个木块组成的木板，我们需要找到将其分解为正方形木块的最小成本。

我们可以沿水平和垂直线切割木板，每次切割会将木板分割成较小的部分。每个切割的成本取决于该切割是否沿着水平或垂直线进行。

让我们用x[1]、x[2]、…、x[n-1]表示沿连续垂直线切割的成本，在水平线上用y[1]、y[2]、…、y[m-1]表示。如果进行一次成本为c的切割，并且该切割通过n个线段，则此切割的总成本将为n*c。

将整个木板切割成单个正方形的成本是使用连续切割将整个木板切割成大小为1x1的正方形木块的成本之和。

求将整个木板切成大小为1x1的正方形木块的最小成本是多少。

示例：假设有一个6×4的网格。

按行切割成本如下：[2 1 3 1 4]

按列切割成本如下：[4 1 2]

答案将是42。

我们应该按照以下顺序开始切割：y5、x1、y3、y1、x3、y2、y4和x2。第一次切割将是成本为y5=4的水平切割。接下来我们将使用x1进行垂直切割。由于该切割通过两个线段（由之前的垂直切割创建），因此其总成本为2*x1 = 2*4。类似地，下一个水平切割(y3)将经过两个线段，并且成本为2*y3 = 2*3。我们可以采用类似的方法继续操作，得到的总成本为4 + 4*2 + 3*2 + 2*2 + 2*4 + 1*3 + 1*3 + 1*6 = 42。

我的方法：从第1行和第2行之间的切割开始检查，然后依此类推。但这显然效率太低。那么如何解决这个问题呢？

- user3343643

Answer 1

选择分割线应按照成本递减顺序，以实现最小总成本。

证明： 任何“不正确”的顺序切割序列必须具有两个连续的切割C1和C2，成本分别为c1和c2，其中c1 < c2且C1在C2之前。如果两个切割线是平行的，则交换它们的顺序对总成本没有影响。 另一方面，如果C1是垂直的而C2是水平的（不失一般性），则我们可以按如下方式进行检查。让V0是应用C1之前的垂直片段数，H0是C1之前的水平片段数。 应用C1然后应用C2的成本是：H0 * c1 +（V0 + 1）* c2 应用C2然后应用C1的成本是：V0 * c2 +（H0 + 1）* c1 第一个表达式减去第二个表达式得到c2-c1，这是正的。换句话说，交换C1和C2会降低成本。 结论：通过一系列交换，可以将任何非有序序列转换为有序序列，从而只能降低总成本。 这完成了优化证明。 注意：如果存在多个成本相同的切割线，则其内部排序根本不影响总成本，如上述计算所示。

- Eyal Schneider

---

如果一刀是水平的，另一刀是垂直的，那么这是否不会影响最小成本？ - user3343643

如果您指的是使用相同成本进行后续切割，那么是的，总成本不会受到影响（c2-c1=0）。 - Eyal Schneider

证明中是否有漏洞？如果能解释一下为什么会被踩就好了。 - Eyal Schneider

嗨Eyal，感谢您提供的整洁证明，但是您能否解释一下被接受答案中提到的其他排序方式，我认为这不是必需的 -> 我无法理解为什么我们需要**cut_groups_ordered_by_most_cut_axis**，如果我不考虑这个**cut_groups_ordered_by_most_cut_axis**排序，我无法得到任何实际影响的测试用例。 - codeomnitrix

@codeomnitrix：我同意，看起来Migol的解决方案有一个不必要的步骤。我提出的证明表明，通过交换相同成本的相邻切割（delta=c2-c1=0），总成本不会受到影响。 - Eyal Schneider

Answer 2

这个问题可以通过贪心算法来解决。

只有1条规则：按照切割成本的递减顺序选择，如果两个或多个成本相等，则任选一个。 以下是Python解决方案：

M, N = map(int, raw_input().strip().split(' '))
Y = map(int, raw_input().strip().split(' '))
X = map(int, raw_input().strip().split(' '))

Y.sort(reverse=True)
X.sort(reverse=True)

y_cut = x_cut = 1     #To count the number of segments
cost = i = j = 0

while i < X.__len__() and j < Y.__len__():
    if X[i] >= Y[j]:
        x_cut = x_cut + 1
        cost = cost + (X[i]*y_cut)
        i = i+1
    else:
        y_cut = y_cut + 1
        cost = cost + (Y[j]*x_cut)
        j = j+1

while i < X.__len__():
    cost = cost + (X[i]*y_cut)
    i = i+1

while j < Y.__len__():
    cost = cost + (Y[j]*x_cut)
    j = j+1

print cost

- Yogesh Yadav

Answer 3

尽管这个问题已经得到了回答，但我写这篇文章是为了提供一个非正式的、直观的解释：

我们需要进行(n-1)*(m-1)次切割，所以我们只需要决定先选择哪个切口。

假设我们可以在两个成本分别为c1和c2的切口C1和C2之间选择。假设c1>c2。让整个事情的总当前成本表示为C

如果我们在此步骤之后选择C1，则至少会增加c1的成本（取决于您是否在下一步中添加它）到整个成本C中。 如果我们在此步骤之后选择C2，则至少会增加c2的成本到整个成本C中。

因此，我们可以说，我们可以贪心地选择现在的C1，因为选择稍后的C1比选择稍后的C2更糟糕。

因此，我们按成本的递减顺序选择，而不考虑切口的类型（水平、垂直）。

- Aman Deep Gautam

Answer 4

这是我在Python 2中使用贪心算法的方法。

1. 为了最小化成本，必须首先削减最昂贵的位置
2. 削减次数为（M-1）+（N-1）
3. 内部顺序无关紧要。因为最终所有位置都将被削减
4. 跟踪每个维度（nx，ny）中当前削减次数

代码

M,N = [int(x) for x in raw_input().split()]
CY = sorted([int(x) for x in raw_input().split()], reverse=True)
CX = sorted([int(x) for x in raw_input().split()], reverse=True)
nx = 1
ny = 1
minC = 0
i = 0
j = 0
total = M - 1 + N - 1
for _ in range(0,total):
    #j == N - 1 to check if CX is exhausted
    if (j == N - 1 or (i != M -1 and CY[i] > CX[j])):
        minC += CY[i]*nx
        ny += 1
        i += 1
    else:
        minC += CX[j]*ny
        nx += 1
        j += 1

print minC%(1000000000+7)

- Steven

Answer 5

只需按照成本递减的顺序选择切割线，以下是C++代码：

代码：

#include <bits/stdc++.h>
using namespace std;

int main() {
long int t;
cin >> t;
while(t--){
    long long int m,n,*x,*y,i,j,sum,cx,cy,modu = 1000000007;
    cin >> m >> n;
    x = new long long int[m-1];
    y = new long long int[n-1];
    for(i=0;i<m-1;i++)
    cin >> x[i];
    for(i=0;i<n-1;i++)
    cin >> y[i];
    sort(y,y+n-1);
    sort(x,x+m-1);

    i=m-1-1;sum=0;j=n-1-1;cx = 1;cy =1;
    while(i>=0 && j >=0){

         if(x[i] > y[j]){
            sum += (x[i]*cy)%modu;
            cx++;
            i--;
        }
        else{
            sum += (y[j]*cx)%modu;
            cy++;
            j--;
        }
    }

    while(i>=0){
        sum += (x[i]*cy)%modu;
        i--;
    }
    while(j>=0){
        sum += (y[j]*cx)%modu;
        j--;
    }

    cout << sum%modu << endl;
}
return 0;
}

- pola sai ram

Answer 6

嗯，看起来这很简单。因此，您需要进行所有切割并最小化最昂贵的切割次数，您只需按其成本对它们进行排序。

不过有一个问题 - 如果您有相同价格的切割，则需要将它们分组。假设您必须进行5次每次6元的切割，其中4次在列上，2次在行上，而板子未被切割。如果您先切2行，则成本为2 * 6 + 4 * 3 * 6 = 14 * 6。如果您以另一种方式进行，则会得到4 * 6 + 2 * 4 * 6 = 12 * 6。

规则是首先进行高价切割，并且首先沿着其中大部分的轴进行切割。

编辑：为了跟踪您有多少个切片，您需要跟踪您对其他轴的切割。如果您已经在行上进行了3次切割，则在列上进行切割将需要3 + 1次切割。如果您已经切割了5列和3行，则再切割一行将始终必须通过每个列切割线，这意味着您必须切割5 + 1次。

编辑2：由于我的示例是不正确的，因此这是使用问题中的情况的外观：

cut_x = [2, 1, 3, 1, 4]
cut_y = [4, 1, 2]

list_of_cuts_grouped_by_cost_descending = [[x5, y1], [x3], [x1, y3], [x2, y2, x4]]

cut_groups_ordered_by_most_cut_axis = [[x5, y1], [x3], [x1, y3], [x2, x4, y2]]

return cut_groups_ordered_by_most_cut_axis.flatten

- Migol

---

请通过示例或伪代码算法进行更详细的解释，以便更好地理解。 - user3343643

我认为你误解了问题。 - user3343643

如何跟踪该切割正在穿过多少个线段？您上面没有提到吗？ - user3343643

我正在要求以问题中讨论的示例为例进行解释，而不是您自己创建的示例。 - user3343643

嗨Migoi，我不明白为什么你需要cut_groups_ordered_by_most_cut_axis，我没有找到任何测试用例会受到影响，如果我不考虑这个cut_groups_ordered_by_most_cut_axis的排序。 - codeomnitrix