So I framed a DP described by the following code: Link
The subproblem I framed was that dp[i] is the most profit that one can get if he plays i-th match. If we play i-th match, then we can either
Play (i-1)th match and not play the one before that, then use the best answer we have for dp[i-3] OR
Don’t play (i-1)th match and instead choose whatever was best (i-2) matches i.e dp[i-2]
When we have filled the whole dp array we select the maximum element in the array. Three subtasks give AC for this but the rest 7 fail. What is wrong with the logic?
Also on an unrelated note, what is the cutoff for ZCO usually? Whole 2 problems? How hard is it to get into IOITC?
Your program doesn’t check all the cases.
Your logic is partially correct.There exists a better,simpler and easily implemented DP solution for this.
Here is the logic:
dp(i,j) denotes the best optimal answer to the problem if we select the i th match with j more matches which can be selected consecutively.
We will call max(dp(0,1),dp(1,1)) for the required optimal answer.
dp(i,j) = a[i] + max( dp(i+1,0), dp(i+2,1), dp(i+3,1) ) // if j is 1.
= a[i] + max( dp(i+2,1), dp(i+3,1) ) // if j is 0.
Hope this helps you.
Sorry, but i can’t post the exact code. You have to do this by yourself.
Thanks for the answer, but I want the flaw in my code, not the correct answer. Could you please give me a test case where my code does not give the optimal answer?