Codeforces 699C - Vacation

help
1

Problem link: Problem - 698A - Codeforces

I’m new to dynamic programming and I didn’t really understand the editorial. It would be appreciated if someone could explain it along with some code.
Thanks!

2

Let dp[i][j] denote the minimum number of days she’ll rest if she did activity j before.
if j is 1, she did a contest, and if j is 2 she went to the gym, and j=0 if she rested
seq[i] is the 0 indexed input. basically stores what she can do on the i+1th day.

for(int i=1;i<=n;i++){
        dp[i][0]=min({dp[i-1][0],dp[i-1][1],dp[i-1][2]})+1; //she can take a rest, anytime, 
 //    so we take the minimum of all 3 possibilities and add 1 for today's rest
        dp[i][1]=1e9;//just set it to a large value
        dp[i][2]=1e9;//We'll change it if it's possible
        if(seq[i-1]&1){   //if she can do a contest today
            dp[i][1]=min(dp[i-1][2],dp[i-1][0]);//minimum of resting yesterday or gyming yesterday
        }
        if(seq[i-1]&2){//if she can gym today
            dp[i][2]=min(dp[i-1][1],dp[i-1][0]);//minimum of resting yesterday or 
           //giving a contest yesterday
        }
  }
4 Likes