竞争规划问题中的布尔矩阵问题在Cohesity的候选测试中的应用

Question

给出了宽度w和高度h的0-1矩阵.0代表黑色，1代表白色。把它想象成条形码。如果整个列都填充了1s，那么它就是条形码上的白色条形码。如果n个连续列填充0，那么它将表示一个宽度为n的黑色条带，现在矩阵不完美(有些列不是完全白色或完全黑色，即它们有一些不规则)。

用1交换单个0的成本是1，反之亦然。

给出x和y，其中x是最小宽度，条形码中的条带必须有，y是最大宽度。你必须找到将原始不完美矩阵转换为满足x和y约束的有效条码矩阵所需的最小成本，即每条条形码的宽度在x，y之间。

蛮力回溯不起作用，得到TLE。

Answer 1

假设一列可能是(1) b中的一列，是黑带中最右边的一列，(2) w是白色条形中最右边的一列。让C是一个函数，使用预先计算的列前缀和计算在O(1)时间内将一系列列转换为白色或黑色。让f(i, type)表示条形码到i第四列的最小成本，当该列是type类型时。然后：

f(0, b) ->
  Infinity if x > 1 else C(0, 0, b) 

f(0, w) ->
  Infinity if x > 1 else C(0, 0, w)

f(i, b) ->
  min( C(j, i, b) + f(j - 1, w) )

f(i, w) ->
  min( C(j, i, w) + f(j - 1, b) )

for j = (i - y + 1) to (i - x + 1)

(显然，f(i)对于i小于零将是无效的，就像跨越第一个索引左边的范围的成本一样)。