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)↵
↵
↵
↵
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)?
↵
↵
