codeforces 455 A Boredom

Tags: algorithms, dynamic programming

The solution I have developed is a dynamic programming twist.

From the problem specification it is obvious to see that we can run a loop upto 10^5 and calculate max points using a recurrence relation like this,

p[i] = max(p[i-1], p[i-2] + f[i] * i)

The question when we choose a[i], it deletes both i-1 and i+1. Then, why the recurrence relation is only depending on i-1 and i-2 should not we also include i+1.

When we have only 1 number say a[0]

Then solution is a[0]

When we have two numbers max points is max(a[0],a1)

When we have 3 numbers max points is max(a1, a[0]+a[2])

i+2 does get included implicitly.

Comments