evilbuggy's blog

Tutorial on Broken Profile DP
By evilbuggy, history, 8 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?
»
8 years ago, hide # |
 
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
»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

how to solve this

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

Thanks you very much

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

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

→ Reply
»
6 years ago, hide # |
 
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
»
6 years ago, hide # |
 
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
»
6 years ago, hide # |
 
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