我需要这个C ++算法一些帮助 [英] I require some assistance with this C++ algorithm
问题描述
我试图解决一个算法问题，但我无法找到解决办法......
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.
有两排灯和N的; 10000列，像这样：
There are two rows of lamps and N < 10000 columns, like so:
11011
11011
或
11101101111000101010
01111101100000010100
这些灯可以是开（1）或关（0）。
These lamps can be "on" (1) or "off" (0).
这所有关闭（0），该方案已输出的步数用了以达到所需的配置开始
Starting from all off (0), the program has to output the number of steps it took to reach the desired configuration.
一个步骤可以是：
- 在触发一盏灯
- 拨动两个灯，一个在另一个之上（在同一列）
- 切换n个连续的灯在同一行中，也可以是整行，也可以是只有两个（或一个如上面所解释）
我计算，该算法应该简单地计算需要来切换灯完全脱落的步骤的数量，这将是与在正确的顺序。也是我的猜测是，试图找到漏洞，超过一灯即序列具有相同的状态，然后切换的。但它变得复杂，因为有两排...
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最近发布一个链接到原始问题语句，事实证明，你被允许开关灯来回。只有我下面的解决方案工作，如果你被允许只在开关灯。
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:
- 关闭1的最大连续运行在上排在一个移动
- 关闭1的下排中最大的连续运行在一个移动
- 如果我= j和灯U [i]和L [J]接通，然后就可以关闭在一个移动交换机既有
当然，基本情况是 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），而不是重新计算。
Memoization
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.
这篇关于我需要这个C ++算法一些帮助的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
