A DP optimization
Difference between en1 and en2, changed 68 character(s)
Problem: [1D dp speedup]: (http://dmoj.ca/problem/cco19p4)

This dp satisfies the property $dp[i]=max_{i<j} (dp[i]+C[i][j])$, where $C[i][j]$ satisfies quadrangle inequality. How can I optimize to O(n log n) or O(n)?
(http://dmoj.ca/problem/cco19p4)


History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English overACer 2020-01-20 09:00:35 966
en2 English overACer 2020-01-20 08:50:43 68
en1 English overACer 2020-01-20 08:48:49 239 Initial revision (published)