joker70's blog

LightOj 1011
By joker70, history, 7 years ago, In English

I have learn DP recently. I am practicing DP in this OJ. Now, I am stuck on this problem.

In this problem I have to find the maximum summation of cells such that any two cells don't have the same row or column.

So, I will use recursion from top of the matrix. When using recursion I got to check if that cell is available or not, i.e. that cells row and column has not previously been used. How can I do that?

Tags #dp
  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
7 years ago, # |
← Rev. 3   Vote: I like it +4 Vote: I do not like it

Unable to parse markup [type=CF_TEX]

, so you can use bitmasks to store which columns are available. Go row by row and each time select one column among the ones available, updating DP as necessary. I'll post code if necessary.

As a side note, this problem can also be solved much faster with min-cost max-flow, though it's obviously overkill.

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

    Sorry , I didn't understand your technique. Can you please describe your technique? I would really appreciate it?

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

      The DP is

      Unable to parse markup [type=CF_TEX]

      , and it stores the maximum value we can achieve when we have processed i rows and used the columns described by bitmask mask. Then when we process the next row, we choose a column j not present in bitmask mask, and check if

      Unable to parse markup [type=CF_TEX]

      , where A[i][j] denotes the value at row i, column j (rows and columns are numbered from 0).
      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How can I store the number of columns in mask?

        And why did you check DP[i][mask] + A[i][j] > DP[i+1][mask+j] ?

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

          If you've never read about bitmasks, I recommend you read about them. For example, you can try this blog -> Bitmasks for beginners.

          In short, each bit represents one element. In this case, 1 for the bit j means column j has been used. And

          Unable to parse markup [type=CF_TEX]

          is not actually addition, it means mask with bit j set to 1, it's just easier to write it that way than writing

          Unable to parse markup [type=CF_TEX]

          .
          → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How can i solve this problem recursively without bitmask. Actually I am beginner at dp and practicing from lightoj.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can keep a visited array, which would store which row or column have already been visited.

    → Reply