Question

Hello,
I was solving this problem and firstly I formulated recursion 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 code shows WA on test 7. I think I doing some mistake while saving the answer. Any help would be highly appreciated.
Thanks :)

Accepted Answer

1

vector<int> fs(n);
vector<int> c(n);
vector<vector<int> > dp(n, vector<int>(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";

link

answered 30 May '18, 12:45

4★meet2mky
201●3
accept rate: 26%

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

(30 May '18, 12:50) meet2mky4★

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

(30 May '18, 13:50) dishant_185★

Yes! If you give me your recursion formula.

(30 May '18, 14:43) meet2mky4★

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.

(30 May '18, 16:49) dishant_185★

If i'm not wrong for each j you may need to find two optimal(means they are best choice for cost) index i1 < i2 < j such that frameSize[i1] < frameSize[i2] < frameSize[j] and this will lead to O(n^3) time complexity.I'm still not able to find the transition function from one state to another state.

(30 May '18, 20:38) meet2mky4★

I guess my solution is completely wrong. Thanks for all the time and effort :)

(30 May '18, 21:17) dishant_185★

showing 5 of 6 show all

Accepted Answer

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

Sorry for bad english

Help in C. Three Displays

Follow this question

Related questions