Need Help with 626F.

Правка en1, от AP_222, 2018-06-23 19:33:05

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.

Теги #dp

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский AP_222 2018-06-23 19:38:13 67
en1 Английский AP_222 2018-06-23 19:33:05 793 Initial revision (published)