跳转至

四边形不等式

四边形不等式的定义

当对于 \(a,b,c,d\) 满足 \(a\le b\le c\le d\) 时，

\[ w(a,d)+w(b,c)\ge w(a,c)+w(b,d) \]

称 \(w\) 满足四边形不等式。

第一类DP优化

\[ f_i=\min_{j<i}\{f_j+w(j,i)\} \]

决策单调性

指的是 \(f_i\) 的决策点 \(p_i\) 满足单调性，可以证明只要 \(w\) 满足 "四边形不等式" 就一定满足决策单调性。

证明

考虑 反证。

我们令 \(c < d\) ，且 \(p(d) < p(c)\) ，为了方便表示令 \(a = p(d), b = p(c)\) 。

所以此时一定满足 \(a < b < c < d\) ，此时必然满足：

\[ \begin{align} w(a,d) \le w(b,d) \\ w(a,c) \ge w(b,c) \end{align} \]

\((1) + (2): w(a,d) + w(b,c) \le w(b,d) + w(a,c)\) 。 此时与四边形不等式相反，所以不成立。

算法实现

单调队列 维护决策集合 \(P\)

单调队列中储存了一个三元组 \((l,r,j)\) ,表示,从 \(l\) 到 \(r\) 的最优决策点都为 \(j\)

对于每一个 \(i\in [1,n]\) ，执行下面操作：

  1. 删除无效队头：当队头为 \((l,r,j)\) ，若 \(r\le i-1\) ，说明当前对头对于答案无效，弹出对头。否则将 \(l\) 设为 \(i\) 。

  2. 取出队头的最优决策点，更新当前 \(f_i\) 。

  3. 插入新元素: \(i\) 。

  4. 取出当前队尾 \((l,r,j)\) 。

  5. 若 \(f(l)+w(i,l)\le f(j)+w(j,l)\) ，则删除队尾，回到第一个操作。

  6. 用二分在 \([l,r]\) 中找出\(pos\),使 \(pos\) 前此决策优，\(pos\) 后 (包含 \(pos\) ) \(i\) 更优，将 \((l,r,j)\) 修改为 \((l,pos-1,j)\) 。

  7. 将 \((pos,n,i)\) 放入队尾

时间复杂度 \(O(n\ log\ n)\) 。

代码实现 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
int n;
int l,r,q[N];
int L[N],R[N];
int w(int x,int y);
void solve(){//写法一，加入f[0]
    l=1,r=1,q[1]=0;
    L[0]=1,R[0]=n;
    for(int i=1;i<=n;i++){
        while(l<=r && R[q[l]]<i) //弹出队首无用项
            l++;
        f[i]=w(q[l],i);
        while(l<=r && w(i,L[q[r]])<=w(q[r],L[q[r]]))//弹出队尾无用项 
            r--;
        int ll=L[q[r]],rr=n+1;
        while(ll<rr){//二分获得pos
            int mid=ll+rr>>1;
            if(w(i,mid)<=w(q[r],mid)) rr=mid;
            else ll=mid+1;
        }
        if(ll>n) continue;
        R[q[r]]=ll-1;
        q[++r]=i;
        L[i]=ll,R[i]=n;
    }
}

void solve(){//写法二，不加入f[0]
    l=1,r=0;
    for(int i=1;i<=n;i++){
        int ans=n+1;
        L[q[r]]=max(L[q[r]],i);
        while(l<=r && w(i,L[q[r]])>=w(q[r],L[q[r]]))//弹出队尾无用项 
            r--;
        if(l<=r && w(i,R[q[r]])>=w(q[r],R[q[r]])){
            ans=R[q[r]]+1;
            int ll=L[q[r]],rr=R[q[r]];
            while(ll<=rr){//二分获得pos
                int mid=ll+rr>>1;
                if(w(i,mid)>=w(q[r],mid)) ans=mid,rr=mid-1;
                else ll=mid+1;
            }
            R[q[r]]=ans-1;
        }
        if(l>r) q[++r]=i,L[i]=i,R[i]=n;
        if(ans!=n+1) q[++r]=i,L[i]=ans,R[i]=n;
        while(l<=r && R[q[l]]<i) //弹出队首无用项
            l++;
        L[q[l]]=i;
        f[i]=max(f[i],w(q[l],i));
    }
}

分治

假设已知 \([l,r]\) 的最优决策在 \([L,R]\) 上。

定义 \(mid=l+r>>1\) ,设 \(dp(mid)\) 的最优决策为 \(p\) ,根据决策单调性,可知 \([l,mid−1]\) 的最优决策在 \([L,p]\) 内, \([mid+1,r]\) 的最优决策在 \([p,R]\) 内。

于是将问题分割成了同类型的规模更小的问题，便可递归分治。

时间复杂度 \(O(n\ logn)\) 。

代码实现 

1
2
3
4
5
6
7
8
9
int w(int j,int i);
void DP(int l,int r,int ll,int rr) {
    int mid=l+r>>1,k=ll;
    for (int j=ll;j<=min(rr,mid-1);j++)//寻找当前决策点
        if (w(j,mid)<w(k,mid)) k=j;
    f[mid]=w(k,mid);
    if(l<mid) DP(l,mid-1,ll,k);
    if(r>mid) DP(mid+1,r,k,rr);
}

第二类DP优化

\[ f_{i,j}=\min_{i\le k \le j}\{f_{i,k}+f_{k+1,j}\}+w_{i,j} \]

决策单调性

当 \(i<i'\le j < j'\) , 满足：

\(P_{i，j'}\le P_{i',j}\) 且 \(P_{i,j-1}\le P_{i,j}\le P_{i+1,j}\)

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int w(int j,int i);
for(int i=1;i<=n;i++) f[i][i]=f[i+1][i]=f[i][i-1]=0,p[i][i]=i;
for(int len=2;len<=n;len++){
    for(int i=1;i+len-1<=n;i++){
        int j=i+len-1;
        for(int k=p[i][j-1];k<=p[i+1][j];k++){
            if(f[i][j]>f[i][k-1]+f[k+1][j]+w(i,j)){
                f[i][j]=f[i][k-1]+f[k+1][j]+w(i,j);
                p[i][j]=k;
            }
        }
    }
}
cout<<f[1][n]<<'\n';