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

Wunder fund : Problem D . Dp solution
Автор AtomRush, история, 10 лет назад, По-английски

Problem LINK I am not able to understand the DP solution of this problem.What does the state represent ? Some solution Links using this DP First Second Third

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

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

HELP

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

I think this was asked a week ago. The OP perhaps deleted the thread, cannot find it now.

The 2 states are (It's a tree DP, so for each vertex i, we consider only its subtrees and itself):

  1. Maximum number of edges with the vertex not "full" (ie. connected to no more than 1 vertex, the vertex can still connect to the parent).
  2. Maximum number of edges with the vertex "full" (ie. connected to 2 vertices already).
→ Ответить