dp[i] - profit from the opening restaurants up to the i-th position. dp[i] = max(dp[i - 1], p[i] + max[dp[j], j <= A and distance between i and j at least k]). Segment trees are helpful to find maximum profir for the positions to th elft of the current. So we use tree of maximums. To satisfy the second property (distance at least k), for the current position you should determine position A, where m[i] - m[A] >= k, this can be done using binary serach (lower_bound in C++).
-- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
