AP_222's blog

By AP_222, history, 6 years ago, In English

I was trying to understand open ande closed interval trick in dp problem 626F through this article, http://codeforces.com/blog/entry/47764 Please have a look at it problem 626F. I don't understand what it means to place ai in it's own group, in comment it was mentioned, opening a new interval and closing it so it's imbalance should be zero then why we're taking val = k+j.(ai — ai-1) as new state.

"val = k + j(ai - ai-1)" "We place the current number ai in its own group : Then, dp[i][j][val] +  = v."

And i was unable to understand this too, why j.v We place the current number ai in one of the open groups, but not close it : Then, dp[i][j][val] +  = j·v (we choose one of the open groups to add ai.)

can anybody help me please. It's important.

can anybody explain what we're doing here, in detail if possible.

Full text and comments »

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