math - 优化:最小化绘画错误

Question

您将获得一个 m*n 网格，其中每个单元格都标记为“b”或“w”。你还会得到黑色和白色的颜料。您可以使用 k 个笔画，每种颜色(黑色或白色)，笔画被定义为来自同一行的连续未着色单元格的着色(这意味着笔画不能超过行的长度，如果您在该笔划结束的那一行结束之前拿起你的画笔)。目的是尽量减少错误的数量，如果您用错误的颜色绘制单元格或单元格仍未绘制，则会发生错误。最优策略是什么？

Answer 1

知道一行问题的解决方案(给定 BW 行上 k 个笔画的最小错误数是多少)可用于解决问题。

对于每一行，列出给定笔画数的错误数k_i = [0, 1, ..., min k needed to cover i-th row] .现在我们有 n列表(不同大小)。要找到在哪些行中使用 'k' 笔画，迭代弹出 k 就足够了。从列表开始的元素，其中笔画覆盖了大多数单元格。

所以，主要任务是解决一行问题，我不确定如何:-)

令 C 为连续颜色变化的次数。比覆盖行的最小笔画数是 ceil( (C+1)/2 ) .这可以通过用第一个笔画替换笔画颜色来完成，以覆盖最后一个笔画中最远变化之间的整行和下一个笔画。第一个笔划具有一个(或两个)末端的颜色。

我认为，使用类似的方法，当笔画不够覆盖整行时，可以找到错误数量。必须省略一种颜色的某些范围。这是通过以下方式完成的:

从不在边界上的颜色开始(省略第一笔划)，

有些笔画不在最后一笔的最远变化之间，但
在更密切的变化之间。

我不确定，但似乎找到几个最小的相同颜色部分就足够了，这将成为错误。这些部分离末端多远可能很重要。

那是现在...