evilbuggy's blog

Tutorial on Broken Profile DP
By evilbuggy, history, 6 years ago, In English

Broken Profile DP

My first blog post :) Any constructive feedback is welcome.

  • Vote: I like it
  • +34
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think there is a O(N * M * 2N) solution for this problem. DP[i][j][p] = solution where we currently start at point (i, j) and the first i-bits of p belongs to the (j + 1)-column and the rest of the bits belongs to the j-column. And transitions are similar to the last solution. This utilizes the 2N different values of p and q more efficiently (since in the other solution, p cannot have zero bit before the last set bit, and q cannot have set bit after the row we currently stand in).

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

    This is what I think is the actual idea behind broken profile dp.

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

https://vjudge.net/problem/22385/origin

how to solve this

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

Thanks you very much

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

Is the blog still available? I have trouble with your link.

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

Auto comment: topic has been updated by evilbuggy (previous revision, new revision, compare).

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

Auto comment: topic has been updated by evilbuggy (previous revision, new revision, compare).

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

Auto comment: topic has been updated by evilbuggy (previous revision, new revision, compare).

→ Reply