I was trying out this question from ICPC Asia : Gwalior-Pune Onsite replay 2018, Even Odd Sub-sequence (EOSUBSEQ).
It looks like a straight up DP question, it would be great if someone could point out an editorial or maybe any resource which could help in understanding this question better?
I just divided the problem in 2 parts - odd and even. Just make a dp1 and dp2table for odd and even -
I will explain in short about the odd part, do similarly for even part then -
dp1= arr[i}%2==1 ? arr[i] : 0 (If first element is odd, put dp1 equal to that element ,else dp1=0)
Then just use this formula-
- If((i-(k+1))<0), take that term as 0
- If arr[i] is even, take it as 0
Take some sequence and try it out yourself
The answer is just dp1[n-1] + dp2[n-1]
this makes sense! thank you!