A DP optimization

Правка en2, от overACer, 2020-01-20 08:50:43

Problem: 1D dp speedup: (http://dmoj.ca/problem/cco19p4)

This dp satisfies the property $$$dp[i]=max_{i \lt 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)?

Теги 1d-dp, quadrangle-inequality

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский overACer 2020-01-20 09:00:35 966
en2 Английский overACer 2020-01-20 08:50:43 68
en1 Английский overACer 2020-01-20 08:48:49 239 Initial revision (published)