# Help in C. Three Displays

Hello,
I was solving [this][1] problem and firstly I formulated [recursion][2] which shows TLE on test 11(it obviously should). I then tried saving the answer, approaching the problem like dp. But I don’t know why the

``````
[3] shows WA on test 7. I think I doing some mistake while saving the answer. Any help would be highly appreciated.
Thanks :)

[1]: http://codeforces.com/contest/987/problem/C
[2]: http://codeforces.com/contest/987/submission/38748342
[3]: http://codeforces.com/contest/987/submission/38736017``````

vector fs(n);
vector c(n);
vector<vector > dp(n, vector(3,INT_MAX));
for(int i=0;i<n;i++){
cin>>fs[i];
}
for(int i=0;i<n;i++){
cin>>c[i];
dp[i][0]=c[i];
}
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(fs[i]>fs[j]){
dp[i][1] = min(dp[i][1], dp[j][0]+c[i] );
}
}
}
for(int i=1;i<n;i++){
for(int j=0;j<i; j++){
if(fs[i] > fs[j] && dp[j][1]!=INT_MAX){
dp[i][2] = min( dp[i][2], dp[j][1]+c[i]);
}
}
}
int ans= dp[0][2];
for(int i=1;i<n;i++){
ans = min(ans, dp[i][2]);
}
if(ans==INT_MAX){
cout<<"-1\n";
}else cout<< ans <<"\n";

1 Like

This problem uses similar approach like LIS O(n^2) version

Thanks for the response, but can u point out the mistake in my code?

Yes! If you give me your recursion formula.

I have posted the links in question. Here they are once again:
Using recursion : http://codeforces.com/contest/987/submission/38748342.
Using dp : http://codeforces.com/contest/987/submission/38736017.
I have used something like this : Let cache[i][j] be the minimum cost taking 1,2…i and maximum size being at position j.

Hey! Dishant in your dp you need to make cache[pos][last][second_last] as it might come to pos last with second last chosen or different from before or even not chosen So although answer will be different your code will return the same value. But if you make the dp as I told it would give tle (as it would be O(n^3)) so you should do something like meet2mky said

Here is my code - http://codeforces.com/contest/987/submission/38740788

EDIT : Example test case consider the input
7
1 2 3 4 5 6 7
7 6 5 4 3 2 1
your code is giving output 10 (due to multiple same pos last occurance) but the ans is 6 the cost of last 3 boards 1+2+3=6