四边形不等式
使用范围：区间序列\(DP\)求最小值（一定是最小值）
对于动态规划转移方程
dp[i][j]=min(dp[i][k],dp[k+1][j])+w(i,j);其中\(w(i,j)\)只受\(i,j\)取值影响
如果满足下面两个条件
\(1.\)区间单调性：如果对于\(\forall i \leq i'< j' \leq j,w(i',j') \leq w(i,j)\)(即小区间取值\(\leq\)大区间取值)
\(2.\)四边形不等式：\(\forall i \leq i'< j' \leq j,w(i,j)+w(i',j')\leq w(i',j)+w(i,j')\)
即中的红线总长\(\geq\) 蓝线总长
如果\(w(i,j)\)同时满足区间单调性和四边形不等式
那么\(f(i,j)\)满足四边形不等式
令\(S(i,j)\)为\(F(i,j)\)在取到最优解时的决策点\(k\)
那么决策本身具有单调性，即满足\(S(i,j)\leq S(i,j+1)\leq S(i+1,j+1)\)
用\(j\)代替\(j+1\)得到
\(S(i,j-1)\leq S(i,j)\leq S(i,j+1)\)
转移方程变为
\(F(i,j)=min(F(i,k)+F(k+1,j))+w(i,j);\ (S(i,j-1)\leq k\leq S(i+1,j))\)
可以证明，他将时间复杂度降到了\(O(n^2)\)
什么时候使用四边形不等式？
只需要牢记公式
考试时可以打一张决策表看是否满足上面式子，满足可以使用四边形不等式
\(1.\)序列\(DP\)有时可以使用四边形不等式优化，但仅仅是常数优化
\(2.\)需要注意四边形不等式仅针对求最小值的情况
\(3.\)注意\(S\)数组（下标取值范围）需要初始化,\(S[i][i]=i\)
例题
P1880石子合并
这道题的四边形不等式非常裸，但要注意求最大值不能用四边形不等式，注意到最大值可以使用决策单调性优化
求最大值时\(f[i][j]\)一定是从\(f[i][j-1]\)或\(f[i+1][j]\)转移过来的，所以可以将第三维优化掉
\(Code\)