Someone please suggest a way to precede these kind of problems! I am a lot interested but a beginner programmer! (knows only basics)

If you are new to these types of problems, refer this link.

http://www.iarcs.org.in/inoi/online-study-material/topics/dp.php

See the question is simple dp

Given

n matches you a(1),a(2),a(3)…a(n)

So now what will be the total number of selection of matches a player can play 2^n.

However we have one more constraint that is a player can’t play 3 matches in a row thus it is clear that brute force won’t be suffice and would definitely time out… Hence what we can do is analyze the problem on smaller values of n (actually this is the first step one should follow when dealing with such problems)

So lets for n=4

5 6 3 10

So now what can we do

We can pick first match that is 5

Then second that is 6 and then 4rth that is 10 getting total of 21. Getting any hints want am I doing!

Lets observe the solution

Given a(1),a(2)…a(n)

So there will be two types of solution one having a(1) and other not having a(1)

So if write a function

F(a,b) where a is the match under our observation (we would be iterating the matches one by one) and b the left matches we can continuously play.

So if we take a(1) we can play only one match more in continuity (no 3 matches in a row)

Hence after taking a(1) we can either take a(2) or again start the problem starting from a(3)

So the function

f(a,b)=max( f(a+1,b-1)+matchfeesof(a),f(a+2,b))

Now here maximum value of b=2 hence time complexity would be 2a ie suffice. We are taking b=2 because we can play at most 2 matches in a row

Let’s take example

F(1,2) for matches 5,4,10,7

F(1,2)=max(f(2,1)+5,f(3,2))

So now keep on doing like this for all f(a,b) needed and obtain the answer… Note f(a,0)=0 because if we can play 0 matches in continuity then value if also 0

Hope it clears your problem

Well that was hell lot but I experienced problems with dp too hence I am helping you with such a large explanation.

Phew

Hope it help.

Happy coding

thanks a lot man! got the logic…

But could you please send me the complete code for the solution of this problem. @japoorv

Okay here’s the solution:

http://discuss.codechef.com/questions/57151/zco-dynamic-programming-problems

Regarding implementation:

Keep Fees[0]=0 and store the numbers from 1 to N

The final solution would be stored at

```
Best[0][0]
```