fireblaze777's blog

By fireblaze777, 6 weeks ago, In English

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.

 
 
 
 
  • Vote: I like it
  • +16
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +8 Vote: I do not like it

It can be solved in $$$O(n^3)$$$. Here is a good editorial