How to solve this problem using DP?

1
2

We can probably have dp[n + 1][x + 1], and do operations on that.

dp[i][j] denotes reaching the ith position, using j left moves.

The recurrence is dp[i][j] = max(dp[i - 1][j], dp[i + 1][j - 1]) + a[i]

P.S: Take care of the base cases where j = 0, i = 0 etc

As you can find out, the answer will be max(dp[k][0], dp[k - 2][1]....) until j \le x and i > 1 .

If you can’t understand anything, don’t hesitate to revert back.

1 Like
3

shudn’t the recurrence be dp[i][j]=max(dp[i-1][j-1],dp[i+1][j-1])+a[i]
bcz even if we go left it is considered as a move.

1 Like
4

we can solve this using 2D dp and the dp state would be dp[N][z] , but there is one more thing mentioned in the problem , we can’t make more than one consecutive move to left, so we can use 3D dp to handle it and dp state would be dp[N][z][2].
And each time we will move two options- >
1 → move right
2-> move left , if last move was a right move
and take max of all the options.

At first i forgot about the condition that we r not allowed to make two consecutive moves to the left, but it still got accepted :sweat_smile: , may be due to weak test cases.

But here is the correct approach :slightly_smiling_face:
Code: Submission #88413898 - Codeforces

1 Like
5

No that’s because there is no reason to move left more than once.

In fact you can prove the solution is of the form
RRRR ...RLRLRLRL... RRRR

2 Likes
6

Ohh :sweat_smile:
I just tried to make a counter testcase , but couldn’t come up with one .
It seems like the soln is always of the form mentioned by u .Thanks for clearing it @everule1 :+1:

7

See you require unique states to solve any dp problem, now in this, we need to keep track of which position we are at, how many moves to the left we have made, how many total moves are left, and if our last move was one to the left. Now this would lead to a complexity of n^2 because we are keeping track of how many moves are remaining and the position we are at.

If you observe carefully, in fact we don’t need to memoize how many moves are remaining. That state can be recovered from other states i.e. the position we are at and how many moves we’ve made to the left. Take a look at my recursive function, it will give you a better idea.

8

I guess you misunderstood the reply.

Over here x means the number of times we have already gone to the left.

Thus if we move to the left, we come at that (ith) index from (i + 1) index.
So, if we move to the left, dp[i][j] = dp[i + 1][j - 1] + a[i]

If we move to the right, we come from i - 1 index, and no left moves will be needed. So here, dp[i][j] = dp[i - 1][j] + a[i].

Combining the two equations,
dp[i][j] = max(dp[i + 1][j - 1], dp[i - 1][j]) + a[i] (as we need the maximum value)

I hope you could understand the recurrence @akash_lenka.

My solution if you have any trouble.

1 Like
9

Geez, seeing all you 4 star coders slicing through DP problems like butter makes me wonder if I even belong in Div-1.

1 Like
10

Believe me brother, I too think that

1 Like
11

I think there is no hard need for DP.
i used prefix sum array to solve the problem.

ll n,k,z;
        cin >> n >> k >> z;
        ll a[n],pre_sum[n];
        for (int i = 0; i < n; ++i)
        {
            cin >> a[i];
            if(i==0) pre_sum[i] = a[i];
            else pre_sum[i] = a[i]+pre_sum[i-1];
        }
        ll Max_sum=0,pair_sum=0,Min;
        for (int i = 1; i <= k; ++i)
        {
            Min = min((k+1-i)/2,z);
            pair_sum = a[i] + a[i-1];
            Max_sum = max(Max_sum,(pre_sum[i-1] + pair_sum*Min + pre_sum[k-2*Min] - pre_sum[i-1]));
            //cout << Max_sum << "\n";
        }
        cout << Max_sum << "\n";
1 Like