給定一個元素陣列A，N我們可以對其執行以下型別的更新：
選擇一個并將范圍內的所有元素i加1[i,N]
沒有元素A等于0的最小更新次數是多少。也就是說，對于每個i A[i] != 0
uj5u.com熱心網友回復：
觀察 1：我們應用增量的順序不會改變結果。有了這個觀察，存在最佳增量，其中所有增量都應用于增加的索引。
觀察 2：如果我們有一個正確的解決方案，并且在將增量應用于范圍的那一刻[i, N]，A[i] != 0這個增量替換為增量的解決方案[i 1, N]也是正確的。
考慮到這兩個觀察結果，我們知道有一個最佳解決方案，其中增量從左到右應用，并且每個增量都應用在索引處i，使得A[i] == 0. 這使得以下演算法正確（用偽代碼撰寫）：
increments=0
for i=1 to N
if A[i] increments == 0
increments = 1
這里要在后綴中添加 1，因為我正在回圈增加索引，我只是將多少增量存盤在變數中會影響當前索引，并且碰巧在回圈完成后它還包含答案。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/427534.html
上一篇：字典鍵python