Does this cost function satisfy quadrangle inequality?

Revision en1, by rhezo, 2017-05-10 01:48:40

Suppose I have a cost function w(i, j) whose value depends on some f(j) and value of w(i, j) increases as |j — i + 1| increases. Also we can't compare between w(i, j) and w(p, q) even when |j — i| = |q — p| since that depends upon f(j) and f(q).

The cost function of land aquisition problem from USACO is similar and in the below link it claims that it satisfies quadrangle inequality. Check problem link from example 2 in below link.

https://sites.google.com/site/ubcprogrammingteam/news/1d1ddynamicprogrammingoptimization-parti

So, does my original cost function satisfy quadrangle inequality? I'm confused!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English rhezo 2017-05-10 01:48:40 690 Initial revision (published)