Dynamic Programming21 sections · 916 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[i1]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[i1],dp[i2]+icount[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 i1i-1.