mohamed.gaber's blog

By mohamed.gaber, 15 years ago, In English
please any one solved this problem explain the idea of it please.
thanks in advance.
  • Vote: I like it
  • 0
  • Vote: I do not like it

15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
This problem is simple DP problem
let us consider first that the card is also an envelope, now the problem is what is the maximum number of envlopes that can be stacked in each other and the inner envelope is the card

the recursive formula is like that
Sol[i] = Max ( sol[k] + 1 , Sol[i] )
where k is every envelope that envelope i can be stacked in

so it will be like that

    for(int k = 0; k < N;k++)
    {
        if(Cards[i][0] < Cards[k][0] && Cards[i][1] < Cards[k][1] && DP[i] < Solve(k)+1)
        {
            DP[i] = Solve(k)+1;
        }
    }


i got memory limit exceeded cuz i precomputed this step first ....but in practice session i removed the precomputing step and I got AC