我需要一些帮助这个C ++算法 [英] I require some assistance with this C++ algorithm

问题描述

我试图解决一个算法问题，但我找不到解决方案...

任务是输出最少的步骤需要达到灯的某些配置。

灯有两排， 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）：= 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

您可以计算RU和RL从左到右， code> O（n）时间。

观察结果

，请注意，如果 A [i] [j] 在上一行的末尾有 k_1 c $ c> k_2 零，则 f（i，j）= f（i-k_1，j-k_2） k_1 和 k_2 灯已关闭。

复发关系

观察，如果你想计算 f（i，j）是3种情况：

1. 关闭一次移动上一行中最大连续的1次




3. 如果i = j且灯U [i]和L [j]已打开，则可以同时切换两个




当然，基本情况是 f（0,0） c>

然后为了计算 f（i，j）：<$ p> / 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 
  





Memoization





为了避免为同一个 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:

• toggle one lamp
• toggle two lamps, one above the other (in the same column)
• toggle n consecutive lamps in the same row, it can be the whole row, it can be only two (or one as explained above)

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...

解决方案

Edit:

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.

Definitions

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.

Observations

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.

Recurrence relation

Observe, that if you want to compute f(i, j) there are 3 cases:

1. Switch off maximal consecutive run of 1's in the upper row in one move
2. Switch off maximal consecutive run of 1's in the lower row in one move
3. If i = j and lights U[i] and L[j] are switched on, then you can switch both off in one move

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

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.

Runtime

The simple upper bound is of course O(n^2) because there are at most O(n^2) subproblems.

这篇关于我需要一些帮助这个C ++算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！