Dynamic Programming21 sections · 915 units
Open in Course

Codeforces 455A Boredom - Transition

Take or skip each value

The transition (how we compute each state) extends the formula from unit 1111: dp[i]dp[i] = max(skip excitement ii and keep dp[i−1]dp[i-1], or take excitement ii). If you take excitement ii, you add a[i]a[i] points but must skip a[i]−1a[i]-1 and a[i]+1a[i]+1.

That means your previous choice was from excitement a[i]−2a[i]-2 or earlier. The formula becomes dp[i]=max⁡(dp[i−1],dp[i−2]+i⋅count[i])dp[i] = \max(dp[i-1], dp[i-2] + i \cdot \text{count}[i]). You either skip value ii entirely, or take all copies of it (earning i×count[i]i \times \text{count}[i]) after skipping i−1i-1.