zcmimi's blog
avatar
zcmimi
2020-01-10

四边形不等式

定义

对于任意a_1\le a_2<b_1\le b_2,满足m[a_1,b_1]+m[a_2,b_2]\le m[a_1,b_2]+m[a_2,b_1]

那么m[i,j]满足四边形不等式

要证明m[i,j]满足四边形不等式可以用打表或数学归纳法

区间类2D1D动态规划应用

m[i,j]为动态规划中区间[i,j]的答案

一般是m[i,j]=\min(m[i,k]+m[k,j])(k\in [i,j]),当然\max或其他的也可以

优化的前提是:m满足四边形不等式

一般的区间dp的复杂度是\Theta(n^3)

我们可以优化为\Theta(n^2)

定义s[i,j]为使m[i,j]取得最优解的k

可以证明:s[i,j-1]\le s[i,j]\le s[i+1,j]

那么m[i,j]=\min(m[i,k]+m[k,j])(k\in [s[i,j-1],s[i+1,j]])

复杂度分析:

假设我们现在要求m[i,i+L],

那么我们要枚举的次数是:

(s[2,L+1]-s[1,L])+(s[3,L+2]-s[2,L+1])+…+(s[n-L+1,n]-s[n-L,n-1])=s[n-L+1,n]-s[1,L]\le n

所以总复杂度是\Theta(n)

证明:

对上述s[i,j-1]\le s[i,j]\le s[i+1,j]的证明:

mk[i,j]=m[i,k]+m[k,j],s[i,j]=d

对于任意k<d,有mk[i,j]\ge md[i,j]

(这里以m[i,j]=\min(m[i,k]+m[k,j])为例)

接下来只要证明mk[i+1,j]\ge md[i+1,j],

那么只有当s[i+1,j]\ge s[i,j]时才有可能有mk[i+1,j]\ge md[i+1,j]

(mk[i+1,j]-md[i+1,j])-(mk[i,j]-md[i,j]) \\ =(mk[i+1,j]+md[i,j])-(md[i+1,j]+mk[i,j]) \\ =(m[i+1,k]+m[k,j]+m[i,d]+m[d,j]) \\ -(m[i+1,d]+m[d,j]+m[i,k]+m[k,j]) \\ =(m[i+1,k]+m[i,d])-(m[i+1,d]+m[i,k])

\because m满足四边形不等式

对于i<i+1\le k<dm[i+1,k]+m[i,d]\ge m[i+1,d]+m[i,k]

\therefore (mk[i+1,j]-md[i+1,j])\ge(mk[i,j]-md[i,j])\ge 0

\therefore s[i,j]\le s[i+1,j],同理可证s[i,j-1]\le s[i,j] 证毕

例题:

[NOI1995]石子合并

1D1D 动态规划中的应用

考虑f_r=\min(f_l+w(l+1,r))(l\in [1,r-1])

w(l,r)满足四边形不等式,

k_rf_r的最优决策点,则有:

\forall r_1\le r_2 : k_{r_1} \le k_{r_2}

证明略

这些也可以看作具有决策单调性

但是我们只能知道枚举的下界,不能知道上界

我们可以采用分治算法来解决

work(l,r,k_l,k_r)表示求解f_l~f_r,并知道最优决策点在[k_l,k_r]

类似下方代码:

void work(int l,int r,int kl,int kr){
    int m=(l+r)>>1,k=kl;
    for(int i=kl;i<=min(kr,m-1);++i)
    if(w(i,m)<w(k,m))i=k;
    f[m]=w(k,m);
    if(l<m)work(l,m-1,kl,k);
    if(r>m)work(m+1,r,k,kr);
}

复杂度:\Theta(n \log n)

也可以使用队列实现决策二分栈

「lG 3515」「loj2157」「POI2011」Lightning Conductor为例:

对于每个j,把a_j+\sqrt{i-j}看成关于i的函数f_j

我们要做的就是在所有j\leq i的函数中找到最值

队列实现决策二分栈,按j从小到大依次维护这些函数。

对于其中任意两个相邻的函数f_t,f_{t+1} ,它们都有一个临界> 值k_{t,t+1}

显然序列中的k_{1,2},k_{2,3}...也要严格递增。

否则,如果k_{t,t+1}\ge k_{t+1,t+2},f_{t+1}根本没有> 用。

每次加入f_i的时候:

设队尾为t,如果当前it优(calc(k_{t-1},i)\ge > calc(k_{t-1},t)),那么弹出t

现在来考虑队头h

k_h\le i那么把h弹出

例题

「lG 3515」「loj2157」「POI2011」Lightning Conductor

[JSOI2011]柠檬

上述题目可参考我的题解库https://zt.zcmimi.top

参考文献:

https://baike.baidu.com/item/四边形不等式/7556574

https://oi-wiki.org/dp/opt/quadrangle/

https://www.luogu.com.cn/blog/flashblog/solution-p3515

四边形不等式
comment评论
Search
search