更新时间:2023-11-24 08:40:34
OP最近发布一个链接到原始问题语句,事实证明,你被允许开关灯来回。只有我下面的解决方案工作,如果你被允许只在开关灯。
OP has posted recently a link to the original problem statement, and it turned out that you are allowed to switch lights back and forth. My below solution works only if you are allowed to switch lights only on.
让我们来定义:
U [我]:=第i个光在上排
L [我]:=第i个光下排
A [1] [J]:= subconfiguration的输入配置,你有我灯在上排和j灯的下排的
例如,如果起始状态是:
For example, if the starting state is:
11101101111000101010
01111101100000010100
然后 A [5] [2]
是:
11101
01
其次,让我们定义:
Secondly, let's define:
F(I,J):=最小的移动到关闭的开关所有的灯数A [1] [J]
您有兴趣在计算 F(N,N)
此外,让我们定义:
RU [我]:1在第i个位置结束的上排=最大连续运行
RL [我]:1的下排在第i个位置,则结束=最大连续运行
例如,如果起始状态是:
For example, if the starting state is:
11101101111000101010
01111101100000010100
然后 RU [1] = 1
, RU [3] = 3
, RU [4] = 0
您可以同时计算RU和RL由左到右 O(N)
的时间。
You can compute both RU and RL from left to right in O(n)
time.
首先,注意观察,如果 A [1] [J]
的 K_1
零点在上月底行 K_2
零点在较低的行末,那么 F(I,J)= F(I - K_1,J - K_2)
因为最后 K_1
和 K_2
灯已经关闭。
First, observe that if A[i][j]
has k_1
zeros at the end of the upper row and k_2
zeros at the end of the lower row, then f(i, j) = f(i - k_1, j - k_2)
because the last k_1
and k_2
lights are already switched off.
注意,如果你想计算 F(I,J)
有3种情况:
Observe, that if you want to compute f(i, j)
there are 3 cases:
当然,基本情况是 F(0,0)
,它需要0举动。
Of course, the base case is f(0, 0)
and it requires 0 moves.
然后,为了计算 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
要避免计算 F
为同一我
和Ĵ
在递归调用很多次,只是存储的结果已经计算 F
在哈希表和 O(1)$返回它们C $ C>,而不是重新计算。
To avoid computing f
for the same i
and j
many times during recursive calls, just store the results of already computed f
in a hash table and return them in O(1)
rather than compute again.
简单的上限,当然是为O(n ^ 2)
因为有最多为O(n ^ 2)
子问题。
The simple upper bound is of course O(n^2)
because there are at most O(n^2)
subproblems.