关于四边形不等式的一些看法
序
dp，一样的dp方程，不一样的速度
就像你我天生为人
简介
刷题，是日常的。尤其是在luogu。。大神都在BZOJ
我们在处理dp问题时，常常会出现一个二维的问题，他的dp转移方程是:
这样的问题我们称之为区间dp，是常见的。
但是，朴素的dp无法过掉此题，因为复杂度为(O(n^3)),这是无法容忍的，事实上，我能打出来已经不错了，好的我们下面介绍一下一种优化
四边形不等式
先有一个引理当一个函数(w(i,j))当且仅当对于(a < b le c <d)满足(w(b,c)+w(a,d)>=w(a,c)+w(b,d))时，此函数为凸函数
我们举一个例子 [IOI2000] 邮局
dp的转移方程为(dp[i][j]=min_{i<=k<j}(dp[i-1][k]+w[k+1][j])),其中(w[i][j])为转移的代价
不妨对上面的引理变形
再移项
而这个式子 ，是显然的，比如说，通过一个例子
我们看，当左端点一样是，增加一个右端，会让花费变大，我们证明的时这个花费随着左端点的右移不升，而这，是显然的。
所以我们引出一个四边形不等式 ,由于w是一个凸的函数，而f由w累加，所以f也是凸函数所以 (f[i][j] + f[i + 1][j + 1] leq f[i][j + 1] + f[i + 1][j])
于是有决策点 (s[i-1][j] le s[i][j] le s[i][j+1])
证明 不妨对于$x>y $,有x作为k-1的的决策
故而有 (f[k-1][x]+w[x+1][i]<=f[k-1][y]+w[y+1][i])
而对于(i+1),有 (w[y+1][i]+w[x+1][i+1]>=w[y+1][i+1]+w[x+1][i])
移项，有 (w[y][i+1]-w[y][i]<=w[x][i+1]-w[x][i])
咦，怎么证否了
不对上面的不等号反了。。。。
y+1<x+1,i<i+1 为交叉大于顺着
所以 (w[y+1][i+1]+w[x+1][i] ge w[y+1][i]+w[x+1][i+1])
....
然后有
(f[k−1][x]+val(x+1,i′)≤f[k−1][y]+val(y+1,i′))
所以对于 i',x仍比y优
dp
满足决策单调性
证毕
行吧，以上为扯淡
开始copy
证明 (K[i][j−1]≤K[i][j])时，先假设 (f[i][j−1]) 有最优决策 k=y，再根据(x leq yleq j-1<j)，列出四边形不等式：(f[i][y]+f[i+1][x]≥f[i][x]+f[i+1][y])
在不等式两边添加一定的项试图得到 (f[i][j−1](k=x)+f[i][j](k=y)≤f[i][j−1](k=y)+f[i][j](k=x))
移项可得：(f[i][j−1](k=x)−f[i][j−1](k=y)≤f[i][j](k=x)−f[i][j](k=y))
(∵f[i][j−1](k=y)≤f[i][j−1](k=x))
(∴f[i][j](k=y)≤f[i][j](k=x))
所以整完了，我米勒，事实上，对于满足决策单调性的就好
事实上参见CF321E ，我们在这里有(w(b,c)+w(a,d) le w(a,c)+w(b,d))
是反的！！！
但是我们依然有那个结论 (s[i-1][j] le s[i][j] le s[i][j+1])
神奇吧。。。。但是好多AC此题的人使用了忘情水。。。我会学习的，再次介绍四边形类似的优化
我们对于这个题有笔者简单的自己证明
证明 不妨对于(x>y),有x作为k-1的的决策
故而有 (f[k-1][x]+w[x+1][i]<=f[k-1][y]+w[y+1][i])
而对于(i+1),有 (w[y+1][i]+w[x+1][i+1]>=w[y+1][i+1]+w[x+1][i])
移项，有 (w[y][i+1]-w[y][i] ge w[x][i+1]-w[x][i])
咦，怎么证对了
两边一加，我们得到 (f[k-1][x]+w[x+1][i+1]<=f[k-1][y]+w[y+1][i+1]),故(s[i][j] le s[i][j+1]),
那个(s[i-1][j]<=s[i][j])的话，我们可以通过数学归纳法证明。
待证
但是事实验证是对的。。。
嵬
至于嵬。只是我聊记某人罢了
我会做补充的，对于不完善的地方。