给您一个 m*n 网格，其中每个单元格标记为“b”或“w”。你也会得到黑白颜料。您可以使用 k 笔画，每种颜色（黑色或白色），笔画定义为同一行中连续无色单元格的着色（这意味着笔画不能超出行的长度，如果您在该行结束之前拿起你的刷子，那是该笔划的结束）。目的是尽量减少错误的数量，如果您用错误的颜色绘制单元格或单元格保持未绘制，则会发生错误。最优策略是什么？
问问题
129 次
1 回答
0
知道一行问题的解决方案（给定 BW 行上 k 笔画的最小错误数是多少）可用于解决问题。
对于每一行，列出给定笔画数的错误数k_i = [0, 1, ..., min k needed to cover i-th row]。现在我们有了n（不同大小的）列表。k要找出在哪些行中使用“k”笔划，从列表的开头迭代弹出元素就足够了，其中笔划覆盖了大多数单元格。
所以，主要任务是解决一行问题，我不知道如何:-)
设 C 为连续颜色变化的次数。比覆盖行的最小笔画数是ceil( (C+1)/2 ). 这可以通过交替笔画颜色与第一个笔画来完成，以覆盖整行和最后一个笔画中最远变化之间的下一个笔画。第一个笔画具有一个（或两个）末端的颜色。
我认为，通过类似的方法，当没有足够的笔画覆盖整行时，可以找到错误的数量。必须省略一种颜色的某些范围。这是通过以下方式完成的：
从不在边界上的颜色开始（省略第一个笔画），
有些笔画不是在最后一笔画的最远变化之间，而是在更近的变化之间。
我不确定，但似乎找到几个最小的相同颜色部分就足够了，这将是一个错误。可能这些部分离末端有多远很重要。
那是现在...
于 2012-09-06T17:12:13.463 回答