DP的四边形不等式及决策单调性优化
四边形不等式
设函数(w(x,y))
若对于任意的(aleq bleq cleq d)，满足(w(a,c)+w(b,d)leq w(a,d)+w(b,c))则称函数(w)满足四边形不等式
性质一：
(w)满足四边形不等式当且仅当(w(i,j)+w(i+1,j+1)leq w(i+1,j)+w(i,j+1))
首先，根据四边形不等式的定义，必要性显然，接下来证明充分性
移项可得：(w(i,j)-w(i,j+1)leq w(i+1,j)-w(i+1,j+1))
推广可得：(w(i,j)+-w(i,j+1)leq w(i+k,j)-w(i+k,j+1) (k>0))
(∴w(i,j)-w(i+k,j)leq w(i,j+1)-w(i+k,j+1) (k>0))
(∴w(i,j)+w(i+k,j+1)leq w(i,j+1)+w(i+k,j))
充分性得证
区间包含单调
若对于任意的(aleq bleq cleq d)满足(w(a,d)leq w(b,c))或对于任意的(aleq bleq cleq d)满足(w(a,d)geq w(b,c))，则称(w)满足区间包含单调
常用形式
形式一：(f(i,j)=min(f(i,k)+f(k+1,j)))
假设(f(i,j))的最优决策点为(p(i,j))
定理一：若(f)满足四边形不等式，则(p(i,j-1)leq p(i,j)leq p(i+1,j))
证明：
设决策点(xleq y)
有(f(x,j-1)+f(y,j)leq f(x,j)+f(y,j-1))
两边同时加上(f(i,x-1)+f(i,y-1))得
(f_x(i,j-1)+f_y(i,j)leq f_x(i,j)+f_y(i,j-1))
(f_x(i,j-1)-f_y(i,j-1)leq f_x(i,j)-f_y(i,j))
若(x)优于(y)，则(f_x(i,j)-f_y(i,j)leq0)
(∴f_x(i,j-1)-f_y(i,j-1)leq0)
即在对于(f(i,j-1))的转移中(x)也优于(y)
若(k>p(i,j))，则(p(i,j))在对于(f(i,j-1))的转移中也优于(k)，即(p(i,j-1)leq p(i,j))，不等式后半部分同理
定理一得证
运用定理一可将时间复杂度从(O(n^3))降到(O(n^2))
形式二：(f(i,j)=max(f(i,k)+f(k+1,j)))
将形式一中四边形不等式的符号反向即可
形式三：(f(i,j)=min(f(i,k)+f(k+1,j)+w(i,j)))
定理二：若(w)满足区间包含单调和四边形不等式，则(f)也满足区间包含单调和四边形不等式
证明：
(∵w)满足区间包含单调
(∴w)全为正或全为负
(∴f)也满足区间包含单调
下面证明四边形不等式
当(a=b或c=d)时显然成立
下面对区间长度进行归纳
(1^ob=c)
有(aleq b=cleq d)，设(x为f(a,d))的最优决策点，由对称性，不妨设(xleq b)
(f(a,c)+f(b,d)=f(a,b)+f(b,d)leq f(a,x)+f(x+1,b)+w(a,b)+f(b,d))
(leq f(a,x)+f(x+1,b)+f(b,d)+w(a,d)leq f(a,x)+f(x+1,d)+w(a,d))
(=f(a,d)=f(a,d)+f(b,c))
(2^ob eq c)
有(a<b<c<d)，设(x)为(f(a,d))的最优决策点，(y)为(f(b,c))的最优决策点，由对称性，不妨设(xleq y)
(f(a,c)+f(b,d)leq f(a,x)+f(x+1,c)+w(a,c)+f(b,y)+f(y+1,d)+w(b,d))
(leq f(a,x)+f(b,y)+f(x+1,d)+f(y+1,c)+w(a,c)+w(b,d))
(leq f(a,x)+f(x+1,d)+f(b,y)+f(y+1,c)+w(a,d)+w(b,c))
(=f(a,d)+f(b,c))
定理二得证
形式四：(f(i)=min(f(j)+w(j+1,i)))
可以将(f(i))看作(f(1,i))，根据定理二：只要(w)满足区间包含单调和四边形不等式，(f)也满足区间包含单调和四边形不等式，根据定理一：(s(i-1)leq s(i))就将时间复杂度从(O(n^2))降到了(O(n))
题目：