競爭編碼算法

-3

這是一個持續競爭的問題。
https://www.codechef.com/AUG17/problems/CHEFFA 競爭編碼算法

鑑於陣列A = (A1, A2, ..., AN)，最初具有N個整數在它。現在對於i ≥ 1, if Ai > 0, Ai+1 > 0和Ai+2存在，則他可以將Ai和Ai+1都減1，並將Ai+2增加1。如果Ai+2不存在，但Ai > 0和Ai+1 > 0，那麼他可以將Ai和Ai+1（它將成爲數組的當前最後兩個元素）減1，並在末尾添加一個新元素，其值爲1

使用此操作多次計算A可能生成的不同數組的數量。

假設數組是{2,3,1}：然後：所有可能的排列是：

(2, 3, 1) → (2, 2, 0, 1) 

(2, 2, 0, 1) → (1, 1, 1, 1) 

(1, 1, 1, 1) → (1, 1, 0, 0, 1) 

(1, 1, 0, 0, 1) → (0, 0, 1, 0, 1) 

(1, 1, 1, 1) → (1, 0, 0, 2) 

(1, 1, 1, 1) → (0, 0, 2, 1) 

(2, 3, 1) → (1, 2, 2) 

(1, 2, 2) → (0, 1, 3)

因此，答案是9

注：

我知道，這可使用動態編程完成，但不知道如何，我嘗試使用遞歸，但獲得TLE。我不期望完整的解決方案，但一點點的方向是我需要的。

來源

2017-08-08 Ayush Patel

這是目前的[CodeChef挑戰]（https://www.codechef.com/AUG17/problems/CHEFFA）。在這裏發帖尋求幫助違反了比賽[行爲準則]（https://discuss.codechef.com/questions/18662/does-codechef-have-any-code-of-conduct） – Prune

[「有人能幫助我嗎？」是不是一個有效的SO問題]（https://meta.stackoverflow.com/questions/284236/why-is-can-someone-help-me-not-an-actual-question）。這通常表明，你需要的是半個小時的時間與當地的導師，或通過一個教程，而不是堆棧溢出。 – Prune

@keyvanvafaee：關於你在這裏的編輯，再次有更多報價設備的材料，這不是一個報價。請不要僅將這些添加爲裝飾。 – halfer

考慮以下僞：

result = 1 
queue = {array} 
while queue is not empty 
    array = queue.pop() 
    n = array.length() 
    for i from 0 to n-2 
     if array[i] * array[i+1] >0 
      temp = array 
      temp[i] -= 1 
      temp[i+1] -= 1 
      temp[i+2] += 1 
      if temp not already present in queue 
       queue.push(temp) 
       result += 1 
    if array[n-1] * array[n-2] >0 
     array[n-1] -= 1 
     array[n-2] -= 1 
     array.push(1) 
     if array not already present in queue 
       queue.push(array) 
       result += 1 
print result

值結果將是可能的陣列的數目。對於大尺寸的數組或大數組值，算法可能效率不高。

來源

2017-08-12 11:43:18

我試過使用listoflists但得到TLE，我很確定它可以使用動態編程來完成 –

競爭編碼算法

回答

相關問題