关于四边形不等式的一些看法
序
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 y\leq 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]\)的话,我们可以通过数学归纳法证明。
待证
但是事实验证是对的。。。
嵬
至于嵬。只是我聊记某人罢了
我会做补充的,对于不完善的地方。