更新时间:2023-11-24 08:35:40
OP最近发布了一个指向原始问题语句的链接,允许您来回切换灯光。
让我们定义:/ p>
U [i]:=上一行中的第i个。
L [i]:=下一行中的第i个灯。
A [i] [j]:=输入配置的子配置,其中i个灯位于上排,j灯位于下排。
例如,如果起始状态为:
11101101111000101010
01111101100000010100
然后 A [5] [2]
11101
01
其次,我们定义:
f(i,j):= light off in A [i] [j]
您对计算感兴趣 f(n,n) / code>
此外,我们定义:
i]:=上一行中结束于第i个位置的1的最大连续运行。
RL [i]:=在第i行中结束的下一行中1的最大连续运行。
状态是:
11101101111000101010
01111101100000010100
然后 RU [1] = 1
, RU [3] = 3
, RU [4] = 0
,请注意,如果 A [i] [j]
在上一行的末尾有 k_1
c $ c> k_2 零,则 f(i,j)= f(i-k_1,j-k_2)$ c $因为最后的
k_1
和 k_2
灯已关闭。
观察,如果你想计算 f(i,j)
是3种情况:
当然,基本情况是 f(0,0)$ c c>
f(i,j)
: / p> 如果U [i]关闭://在上一行结尾处跳过零
compute f i-1,j)
else如果L [j]被关闭://在下一行结束处跳过零
计算f(i,j-1)
else
如果i == j // U [i]和L [j]被接通,因为我们跳过末端零,
f(i,j)= min(f(i-RU [i] j),f(i,j-RL [j]),f(i-1,j-1))+ 1
else:
f f(i-RU [i],j),f(i,j-RL [j]))+ 1
为了避免为同一个 i 计算
f
code>和 j
多次在递归调用期间,只是存储已经计算的结果 f
并且返回 O(1)
,而不是再次计算。
简单的上界当然是 O(n ^ 2)
,因为最多有 O )
子问题。
I'm trying to solve an algorithm problem but I cannot find the solution...
The task is to output the lowest number of steps needed to reach a certain configuration of lamps.
There are two rows of lamps and N < 10000 columns, like so:
11011
11011
or
11101101111000101010
01111101100000010100
These lamps can be "on" (1) or "off" (0).
Starting from all off (0), the program has to output the number of steps it took to reach the desired configuration.
A step can be:
I figured that the algorithm should simply count the number of steps it takes to switch the lights completely off, and that would be the same as in the "right" order. Also my guess was to try and find "holes", i.e. sequences of more than one lamp with the same state, and then switching those. But it gets complicated since there are two rows...
However I was completely lost after that point and I require some help...
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.
Let's define:
U[i] := i-th light in the upper row.
L[i] := i-th light in the lower row.
A[i][j] := subconfiguration of the input configuration where you have i lamps in the upper row and j lamps in the lower row.
For example, if the starting state is:
11101101111000101010
01111101100000010100
Then A[5][2]
is:
11101
01
Secondly, let's define:
f(i, j) := minimum number of moves to switch all lights off in A[i][j]
You are interested in computing f(n, n)
In addition, let's define:
RU[i] := maximal consecutive run of 1's in the upper row ending in the i-th position.
RL[i] := maximal consecutive run of 1's in the lower row ending in the i-th position.
For example, if the starting state is:
11101101111000101010
01111101100000010100
Then RU[1] = 1
, RU[3] = 3
, RU[4] = 0
You can compute both RU and RL from left to right in O(n)
time.
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.
Observe, that if you want to compute f(i, j)
there are 3 cases:
Of course, the base case is f(0, 0)
and it requires 0 moves.
Then in order to compute 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
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.
The simple upper bound is of course O(n^2)
because there are at most O(n^2)
subproblems.