### fireblaze777's blog

By fireblaze777, 6 weeks ago,

Hello friends, I was trying to solve this dynamic programming problem. The editorial proposes an $\mathcal{O}(N^4)$ solution to this problem, but I think it could be solved in $\mathcal{O}(N^3)$ time according to the following approach:

$DP[i][j] \rightarrow \text{Max score we can get from subarray }A[i \dots j]$

Say, $i \le e_k \le j \rightarrow$ kth occurence of $A[i]$ between $i$ and $j$, $K \rightarrow$ number of occurrences of $A[i]$ in $[i\dots j]$ . Transitions are as follows.

$\displaystyle DP[i][j]=\max(DP[i+1][j],\sum_{k=1}^{K-1} DP[e_k+1][e_{k+1}-1]+K^2)$

Unfortunately, this approach gives WA. I'd be grateful if anyone could share an $\mathcal{O}(N^3)$ or an intuitively more convincing $\mathcal{O}(N^4)$ solution as I was not able to follow the editorial completely.

• +16

»
6 weeks ago, # |
-10

# include <bits/stdc++.h>

using namespace std; int n;int a[1005]; int solve(int i,int samcnt,int prev){ if(i==n)return samcnt*samcnt; if(i==0){ return solve(i+1,1,a[i]); } else if(prev==a[i]){ return solve(i+1,samcnt+1,a[i]); } else { int op1=1+solve(i+1,samcnt,prev); int op2=samcnt*samcnt+solve(i+1,1,a[i]); return max(op1,op2); } }

int main() { cin>>n; for(int i=0;i<n;i++)cin>>a[i]; cout<<solve(0,0,0); return 0; } I came up with the above recurrence relation! It's working correctly but i don't know how to memoise it! I think using map is a good choice but i don't know how to memoise using map! plz tell me if this relation is correct and send memoised code!

 » 6 weeks ago, # | ← Rev. 2 →   0 I thought you can only pick consecutive plates, i.e. those that form a subarray. how does $kth$ occurence of $A[i]$ work in that case.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Yes say the subarray looks like this A....A.......A...A Now if we want to take all the A's together in one shot then we'll first have to make them consecutive as you said, so we first remove all the elements which occur between any 2 occurences and then take all K occurences together
 » 5 weeks ago, # |   +8 It can be solved in $O(n^3)$. Here is a good editorial
•  » » 5 weeks ago, # ^ |   +8 oh wait I can't read