Блог пользователя asawa_harsh

Unable to solve Atcoder ABC237 Problem F

Автор asawa_harsh, история, 3 года назад, По-английски

Can anyone tell me the dp transitions for this problem ? Even after seeing the editorial I am not able to code.

Problem link

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

we will assume fir, sec, and third are three elements in lis array and fir<=sec<=third. now we'll assume x be the next element, then we'll check which element it replace fir, sec, third or none. you can look at this for reference. Link

→ Ответить
  • »
    »
    3 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    Thanks ! Can u explain base case in your code ? I wrote this as base case but not getting correct output of samples.

    for (int i = 1; i <= m; i++) {

    for (int j = i + 1; j <= m; j++) {

      for (int k = j + 1; k <= m; k++) {

                dp[3][i][j][k] = 1; // Base Case

       }

 }

    }

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I wrote dp[0][m + 1][m + 1][m + 1] = 1 as my base case because initially there will be no elements in lis array and i took m+1 so that all subsequent elements will be less than it so can be instantly inserted in lis array.

      → Ответить