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

Plug Dp
Автор rumman_sust, 10 лет назад, По-английски

I recently heard about plug dp (I don't know what it means). When I tried to solve this problem, I read some Chinese blog where they mentioned plug dp. Can any one inform me about plug dp or how to solve this problem? Thanks in advance. :)

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

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

Can you provide problem description? I can't open link, maybe beacause of Great-Firewall.

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

    Finally it's opened. "　Given a map of N * M (2 <= N, M <= 12) , '.' means empty, '*' means walls. You need to build K circuits and no circuits could be nested in another. A circuit is a route connecting adjacent cells in a cell sequence, and also connect the first cell and the last cell. Each cell should be exactly in one circuit. How many ways do we have?"
    This problem can be solved using dynamic programming on the broken profile. Profile contains at most 12 integers in [0..K] and forms correct bracket sequence. e.g. "122331"
    XXXXXX
    XXX331
    122XXX
    XXXXXX

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

    Here is another link. Let me know if you can able to open it :)

    UPD: Sorry didn't see your comment.

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

This type of DP is better known as a "profile DP" or "frontier DP". Here is a good description of just the high-level concept and here has an example with code.

The question linked is a little more complicated but can be solved with the same concept.

→ Ответить