我正在尝试解决算法问题,但找不到解决方案...
任务是输出达到特定灯配置所需的最少步数。
有两行灯和N < 10000列,像这样:
11011
11011
或
11101101111000101010
01111101100000010100
这些灯可以“开”(1) 或“关”(0)。
从所有关闭(0)开始,程序必须输出达到所需配置所需的步骤数。
一个步骤可以是:
- 打开一盏灯
- 切换两个灯,一个在另一个上方(在同一列中)
- 在同一行切换n个连续的灯,可以是整行,也可以只有两个(或者如上所述一个)
我认为该算法应该简单地计算将灯完全关闭所需的步数,这与“正确”顺序相同。我的猜测也是尝试找到“漏洞”,即具有相同状态的多个灯的序列,然后切换它们。但它变得复杂,因为有两行...
但是在那之后我完全迷路了,我需要一些帮助...
最佳答案
编辑:
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 的最大连续运行
- 如果 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)
子问题。
关于c++ - 我需要一些有关此 C++ 算法的帮助,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18303383/