Help needed on DP problem.. Round 485 DIV2C (Three displays)

Revision en6, by MJSaif, 2024-08-03 10:26:29

987C - Three displays

in this problem, in an array S we need to find three indices (i<j<k) such that 1<=(i,j,k)<=n && Si < Sj < Sk... there is another array C.. && the sum of (Ci,Cj,Ck) should be minimum...

my implementation is below..

define N 1000000007

vector a(3000),c(3000);

vector<vector> dp(3001,vector (4,-1));

ll f(int i,int p,int mx){

if(p==0)    return 0;

 if(i==0){
    if(p==1 && a[0]<mx)     return c[0];
    return N;
 }

 if(dp[i][p]!=-1)    return dp[i][p];

 ll pick=N;
 if(a[i]<mx){
    pick=0ll+c[i]+f(i-1,p-1,a[i]);
 }
 ll no_pick=f(i-1,p,mx);
 return dp[i][p]=min(no_pick,pick);

}

int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int n;      cin>>n;
for(int i=0;i<n;i++)    cin>>a[i];
for(int i=0;i<n;i++)    cin>>c[i];
int ans=f(n-1,3,N);
cout<<(ans==N?-1:ans)<<nl;

return 0;

}

for the test case ,

5

2 4 5 4 10

40 30 20 10 40

the answer is: 90 but my output is: 70

why is my code is not giving the right output.. where should I make a change??

Tags dp, help me, help, memoization

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English MJSaif 2024-08-03 10:26:29 2 Tiny change: 't case ,\n5\n\n2 4' -> 't case ,\n\n5\n\n2 4'
en5 English MJSaif 2024-08-03 10:26:04 6
en4 English MJSaif 2024-08-03 10:24:53 2 Tiny change: 'c(3000);\n vector<' -> 'c(3000);\n\n vector<'
en3 English MJSaif 2024-08-03 10:24:06 6
en2 English MJSaif 2024-08-03 10:22:18 100
en1 English MJSaif 2024-08-03 10:20:49 1292 Initial revision (published)