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

How to solve this problem ?
Автор aviroop123, история, 6 лет назад, По-английски

Problem Link — https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=738&page=show_problem&problem=5931

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

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

Direct the edge from node v to Lv and from Rv to v.

Now the problem becomes "How many ways are there to arrange the vertices such that the arrangement is topologically sorted."

Let dp(v, i) be how many topological sorts with the vertices from v's subtree are there such that there are exactly i vertices behind the vertex v.

Now updating the dp is easy.

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

    I didn't understand your approach very clearly ... I have understood how you have reduced the problem to number of ways to order the vertices that are topologically sorted. But I didn't get what your dp state represents. Can you explain your dp state more clearly and the recurrence ?

    → Ответить