infoarena informatica de performanta

De la cost[i] la cost[i+1], denumind linia curenta cu dp[], tranzitiile se pot scrie asa:

• dp[j] += |j|: sunt |j| unitati de flux pe muchia i - i+1
• dp'[j] = min(dp[j], dp[j - 1]): trimite 1 unitate de flux de la i+1 la Destinatie
• dp'[j] = min{non-negative p}(dp[j - p] + p * lambda): cumpara p unitati
• dp'[j] = dp[j + input[i + 1]]: sunt input[i + 1] unitati de flux venind dinspre Sursa