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

P — Independent Set (Educational DP Contest,Atcoder)
Автор apnakaamkar, история, 5 лет назад, По-английски

Could anyone please explain to me how to solve this dp problem? Link:https://atcoder.jp/contests/dp/tasks/dp_p Please help?

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This can be solved by tree dp concept that dp table can be updated from leaf toward to root. Lets assume you are at node now and define the do table like this. dp[current][0]:possible number of current == black dp[current][1]:possible number of current == white

"current"

/     |  ...  \

"child1" "child2" ... "childK"

If current is black, then all childs should be white:

dp[current][black] = dp[child1][white] * dp[child2][white]*...*dp[childK][white];

If current is white, then all childs color does not matter:

dp[current][white] = (dp[child1][white] + dp[child1][black]) * (dp[child2][white] + dp[child2][black])*...*(dp[childK][white] + dp[childK][black]);

After update all nodes, the last one will be the root node and answer is dp[root][white] + dp[root][black].

My submission: https://atcoder.jp/contests/dp/submissions/12971991

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

    dp[current][black] = dp[child1][white] * dp[child2][white]*...*dp[childK][white]; why u multiplied ?

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

      Because those are independent incidents so total possible way of state is multiplication of all sub incidents' answers. Example: Root(Black:6) = Child1[Black:2] * Child2[Black:3] ==> total 2 * 3 = 6 ways.

      → Ответить