### StrawberryInsha2k's blog

By StrawberryInsha2k, history, 2 months ago, ,

Hello everyone, I have been having a lot of problem in solving this question and I have been looking for any help.

https://codeforces.com/contest/505/problem/C This is the question. Can you please help me find the recurrence relation? If you will read the editorial you will find that they have used relation: dp [ i ][ j ] = (the number of the gems on island i ) + max( dp [ i + j — 1][ j — 1], dp [i + j ][ j ], dp [ i + j + 1][ j + 1]), if i < m , j ≥ 2 but in recurrence relation we used to find out the previous state on (right hand side of the equation because that is how we solve sub-problems ) but here they have related dp[i][j] (current state ) with the state that will be achieved afterwards in the process that is dp[i+j+1][j+1], dp[i+j][j] and dp[i+j-1][j-1]. How are we solving sub-problems here? Can you please help me?

• +2

 » 2 months ago, # |   +3 this is an ac solution watch these relations and see if you understamd these relations. yeah we can only modify the past relations but see in this problem , dp[j][i+j] , dp[j+1][i+j+1] and are modified at every step so while taking max we should also consider them also with dp[j][i].int ans = -1199999 for(int i = 0; i < 32000; i++){ for(int j = max(1, d-250); j < d+250; j++){ dp[j][i] += a[i]; int v = dp[j][i]; ans = max(ans, v); dp[j][i+j] = max(dp[j][i+j], v); dp[j+1][i+j+1] = max(dp[j+1][i+j+1], v); dp[j-1][i+j-1] = max(dp[j-1][i+j-1], v); } } hope it helps