Блог пользователя mohamed.gaber

Автор mohamed.gaber, 14 лет назад, По-английски
please any one solved this problem explain the idea of it please.
thanks in advance.
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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