• 欢迎光临~

浅谈四边形不等式

开发技术 开发技术 2022-11-16 次浏览

四边形不等式

对于(f_i=min(f_j+w(j,i)))

若满足(w(a,d)+w(b+c)ge w(a,c)+w(b,d),aleq b leq c leq d)(f)满足决策单调性

(f_ileq f_j+w(i,j))

(p_i)(i)的最优决策点

(f_{i}= f_{p_i}+w(p_i,i)le f_{p_{i+1}}+w(p_{i+1},i))

(f_{i+1}=f_{p_{i+1}}+w(p_{i+1},i+1)le f_{p_i}+w(p_i,i+1))

两式相加即(w(p_i,i)+w(p_{i+1},i+1)le w(p_i,i+1)+w(p_{i+1},i))

(a=p_i,b=p_{i+1},c=i,d=i+1),即可得(p_ileq p_{i+1}),由此(p)单调不降

再形式化一点,实际上只需满足(w(i,j+1)+w(i+1,j)ge w(i,j)+w(i+1,j+1))即可

综合来看,这其实就是相交小于包含

当然,如果是(max),或则是不等号取反,就是单减的决策点

分治

如果有决策单调性,且没有后效性

设计函数(sovle(L,R,l,r))表示([L,R])一段的决策点为((l,r))

如果(mid)的最优决策点为(P),则递归处理(solve(L,mid-1,l,P),solve(mid+1,R,P,r))

时间复杂度同整体二分

二分

由于决策点序列是单增,对于决策点(i>j),可以用二分找到第一个使得(i)更优的点

具体的用队列维护一个三元组((l,r,p))表示(p)能影响(l,r)

队头就是当前能覆盖(i)的第一个,队列里的元素的(l)都是前一个(l+1),队尾的(r)(n)

寻找(i)的最优决策点时,因为(i)单调,所以可以弹出无用对头

考虑(i)作为决策点,因为(i)在最后,所以把(i)决策点加入队尾,如果在队尾的(l)时队尾劣于(i),则直接弹出队尾

否则用二分找(i)第一个影响的位置并塞入队尾

对于决策递减的

分治法就是左右交换

二分法首先要处理(1)的最优决策点,然后考虑用栈维护就可以了

常见满足四边形不等式

(1.)可以用单调队列,斜率优化的

(2.)(sqrt{i-j})

(3.)区间不同个数,区间数的对数

(4.)(|a_i-a_j|^p)

程序员灯塔
转载请注明原文链接:浅谈四边形不等式
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com