c++ - 我需要一些有关此 C++ 算法的帮助

Question

我正在尝试解决算法问题，但找不到解决方案...

任务是输出达到特定灯配置所需的最少步数。

有两行灯和N < 10000列，像这样:

11011
11011

或

11101101111000101010
01111101100000010100

这些灯可以“开”(1) 或“关”(0)。

从所有关闭(0)开始，程序必须输出达到所需配置所需的步骤数。

一个步骤可以是:

• 打开一盏灯
• 切换两个灯，一个在另一个上方(在同一列中)
• 在同一行切换n个连续的灯，可以是整行，也可以只有两个(或者如上所述一个)

我认为该算法应该简单地计算将灯完全关闭所需的步数，这与“正确”顺序相同。我的猜测也是尝试找到“漏洞”，即具有相同状态的多个灯的序列，然后切换它们。但它变得复杂，因为有两行...

但是在那之后我完全迷路了，我需要一些帮助...

Answer 1

编辑:

OP 最近发布了原始问题陈述的链接，结果证明您可以来回切换灯光。我的以下解决方案仅在您被允许只打开灯的情况下才有效。

定义

让我们定义:

U[i] := 上排第 i 个灯。

L[i] := 下排第 i 个灯。

A[i][j] := 输入配置的子配置，其中上排有 i 个灯，下排有 j 个灯。

例如，如果起始状态是:

11101101111000101010
01111101100000010100

那么A[5][2]是:

11101
01

其次，让我们定义:

f(i, j) := 关闭 A[i][j] 中所有灯的最小移动次数

你有兴趣计算f(n, n)

此外，让我们定义:

RU[i] := 上行中第 i 个位置结束的 1 的最大连续运行。

RL[i] := 下行中第 i 个位置结束的 1 的最大连续运行。

例如，如果起始状态是:

11101101111000101010
01111101100000010100

然后 RU[1] = 1, RU[3] = 3, RU[4] = 0

您可以在 O(n) 时间内从左到右计算 RU 和 RL。

观察

首先，观察如果 A[i][j] 在上一行的末尾有 k_1 零，而 k_2 在下一行的末尾，然后 f(i, j) = f(i - k_1, j - k_2) 因为最后的 k_1 和 k_2 灯已经关闭。

递归关系

观察，如果你想计算 f(i, j) 有 3 种情况:

1. 在一步中关闭上排 1 的最大连续运行
2. 一次关闭下排 1 的最大连续运行
3. 如果 i = j 并且灯 U[i] 和 L[j] 都打开了，那么你可以一步关闭它们

当然，基本情况是 f(0, 0) 并且它需要 0 次移动。

然后为了计算f(i, j):

if U[i] is switched off: //skip zeros at the end of the upper row
   compute f(i - 1, j)
else if L[j] is switched off: //skip zeros at the end of the lower row
   compute f(i, j - 1)
else           
   if i == j // U[i] and L[j] are switched on because we skipped zeros at the end
       f(i, j) = min(f(i - RU[i], j), f(i, j - RL[j]), f(i - 1, j - 1)) + 1

   else:
       f(i, j) = min(f(i - RU[i], j), f(i, j - RL[j])) + 1

内存

为了避免在递归调用期间多次为相同的i和j计算f，只需存储已计算的的结果f 在哈希表中，并在 O(1) 中返回它们，而不是再次计算。

运行时

简单的上界当然是 O(n^2) 因为最多有 O(n^2) 子问题。