DP #10 Indian National Olympiad Problem

Calvin's Game Problem Code: INOI1301 (Codechef)

Problem Statement: here

Solution: 

Let me make the question clear first. 

You first start with the forward phase, in which you move either zero or more moves.

Once you terminate your forward phase, you start your backward phase and you have to reach cell 1.

Approach: For moving forward, let us keep a dp array as forward_dp. 

For each index > k, we can use the recurrence dp[ind] = a[ind] + max(dp[ind-1],dp[ind-2])

This is easy because for each position, you can either jump one and reach it, or jump 2 and reach it.

Once, we have terminated our forward phase, we now need to return to cell 1. Returning from any index to index 1,  is same as going from cell 1 to that particular index. So, we keep a backward_dp array. 

Base case : backward_dp[1] = a[1]

backward_dp[2] = a[1]+a[2], because you have to ultimately reach cell 1.

Then, we can use the above recurrence and find out the values.

Once both the dp tables are constructed, we can start iterating from index k to the last index and update the maximum ans considering the current index as the last cell of forward phase and beginning of the backward phase. 

ans = max(ans, forward_dp[ind] + backward_dp[ind] - a[ind])

we are subtracting a[ind] because it was added twice, one for each dp computation.

The code:

void solve() { ll n,k; cin >> n >> k; ll a[n+1]; rep(i,1,n+1) cin >> a[i]; ll forward_dp[n+1] = {}; ll backward_dp[n+1] = {}; ll ans = INT_MIN; backward_dp[1] = a[1]; backward_dp[2] = a[1] + a[2]; rep(i,1,n+1){ if (i > k) forward_dp[i] = a[i] + max(forward_dp[i-1],forward_dp[i-2]); if (i > 2) backward_dp[i] = a[i] + max(backward_dp[i-1],backward_dp[i-2]); if (i >= k) ans = max(ans,forward_dp[i] + backward_dp[i] - a[i]); } cout << ans; }