metal_knight's blog

Plug Dp
By metal_knight, 10 years ago, In English

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. :)

Tags dp
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

    UPD: Sorry didn't see your comment.

    → Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply