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!
Could you maybe link the question? Or any official or informal problem statement?
Edit : I am asking for the link of original problem which is similar to USACO problem.
I heard the term quadrangle inequality for the first time while reading the famous DP optimisation blog on CF. So while reading the link mentioned in blog, I couldn't understand why it satisfies quadrangle inequality.