526互联

<学习笔记> 四边形不等式

发布时间 2023-12-20 16:38:46作者: _bloss

四边形不等式

对于任意的 \(l_1\le l_2\le r_1\le r_2\)，满足 \(w(l_1,r_1)+w(l_2,r_2)\le w(l_1,r_2)+w(l_2,r_1)\) 。
若等号恒成立，则称函数 \(w\) 为四边形恒等式。

  • 如何证明

若满足 \(w(l,r-1)+w(l+1,r) \leq w(l,r)+w(l+1,r-1)\)，则 \(w\) 满足四边形不等式。

  • 决策单调性

对于任意的 \(i_1<i_2\) 必然成立 \(opt_{i_1}<opt_{i_2}\)。

  • 区间单调性

对于任意的 \(l \leq l_1 \leq r_1 \leq r\)，都有 \(w(l_1,r_1) \leq w(l,r)\)。

对于一个 \(dp\) 转移方程：

\[f_i= \min_{1 \leq j \leq i} w(j,i) \tag{1} \]

定理一

若 \(w\) 满足四边形不等式，则以问题（1）满足决策单调性。

证明 
可以用反证法证明。

例题：「POI2011」Lightning Conductor

\[f_i=\min_{j \leq i}{-a_j-\sqrt{i-j} + a_i} \]

\(w(l,r)=r−l\) 满足区间包含单调性和四边形不等式，\(h(x)=-\sqrt x\) 是下凸函数，且 \(-a_j+a_i\) 满足四边形恒等式，用到下文性质三，所以 \(f_i\) 满足四边形不等式，可以分治求解。

区间类 2D/1D DP

形如

\[f(j,i) = \min_{j \leq k < i} f(j,k) + f(k+1,i) + w(j,i) \qquad (1\le j< i\le n) \tag{2} \]

状态数为 \(n^2\)，单次转移为 \(n\)，类似于区间合并。

引理一

若 \(w\) 满足区间包含单调性和四边形不等式，则状态 \(f(j,i)\) 满足四边形不等式。

证明

定理二

若 \(w\) 满足区间包含单调性和四边形不等式，问题（3）中的最优决策 \(opt(i,j)\) 满足：

\[\mathop{\mathrm{opt}}(j,i-1) \leq \mathop{\mathrm{opt}}(j,i) \leq \mathop{\mathrm{opt}}(j+1,i). \qquad (j + 1 < i) \]

证明 
当固定 $j$ 时，构成的函数满足四边形不等式，根据定理一得 $opt(j,i)<opt(j,i+1)$。另一侧同理。
所以每次记下最优决策点，转移时只在 $opt(j,i-1) ~ opt(j+1,i)$ 枚举就行，枚举总量为 $O(n)$，所以复杂度 $O(n^2)$。

1D/1D DP

  • 问题

考虑将某个区间拆分成若干个子区间的问题，求代价最小。

那么将列出如下转移：

\[f(i) = \min_{1\leq j\leq i} f(j-1)+w(j,i) \qquad (1\leq i\leq n) \tag{3} \]

状态数 \(O(n)\)，转移复杂度 \(O(n)\)，考虑四边形不等式优化，

若 \(w(i,j)\) 满足四边形不等式，那么 \(f_j+w(i,j)\) 也满足四边形不等式（因为与 \(i,j\) 不包含交叉项），因此这个具有决策单调性。

但是转移必须从前到后，那么只限制了下界，没有上界，所以不可以用分治，那么就需要用二分队列。

如果在此问题上加上 \(m\) 个数限制，那么又有如下转移：

\[f(k,i) = \min_{1\leq j\leq i} f(k-1,j-1)+w(j,i) \qquad (1\leq k\leq m,\ 1\leq i\leq n) \tag{4} \]

定理三

若 \(w\) 满足四边形不等式，那么问题（4） 中的问题满足 \(\mathop{\mathrm{opt}}(k-1,i) \leq \mathop{\mathrm{opt}}(k,i) \leq \mathop{\mathrm{opt}}(k,i+1)\)。

假如 \(w(j,i)\) 满足四边形不等式，那么 \(f(k-1,j-1)+w(j,i)\) 也满足四边形不等式，。那么这个就可以记录最优决策点，将其优化为 \(O(n^2)\)。

求解方法

分治

设 \((l,r,ls,rs)\) 表示 \(f_{l~r}\) 的决策点在 \((ls~rs)\) 之间。我们考虑 \(mid\) 的决策点 \(pos\)，可以暴力求出。然后左右区间的决策点就有了新上下界，然后递归到这两个区间求解，复杂度 \(O(n \log n)\)

二分队列

对于当前状态依赖于前面的状态的，例如问题 \((4)\)，我们就不可以分治，只能二分队列。

因为决策是单调的，那么每个决策点 \(i\) 所处理的问题 \(j\) 也构成一个区间，设三元组 \((i,l_i,r_i)\) 表示 \(i\) 处理的区间为 \(l_i~r_i\)，\(val(i,j)\) 表示从 \(i\) 转移到 \(j\) 的 \(f_j\) 的值，算法如下：

  • 初始化： 将最初的决策点压入队列，比如将 (0,1,n) 压入队列，表示它对于所有点目前它是最优的。

  • 计算： 每次从队首取出第一个满足 \(l_j \leq i \leq r_j\) 的 \(j\)， 有 \(j\) 更新 \(i\)。顺便将所有 \(r_j \leq i\) 的出队。

  • 入队：

    • 设队尾为 \(j\)，如果 \(val(i,l_j) \leq val(j,l_j)\) 则弹出队尾。持续到队列为空或不满足。

    • 如果队列已空，那么直接将决策 \((i,i+1,n)\) 压入。

    • 若不为空，我们还考虑队尾决策 \(j\)，此时对于 \(l_j\) 决策 \(j\) 优于 \(i\)。

      • 如果 \(val(i,r_j) \geq val(j,r_j)\)，那么直接加入 \((i,r_j+1,n)\)。

      • 否则，我们需要找到那个分界点，直接二分出来最小的使 \(val(i,p) \leq val(j,p)\) 的点，将队尾 \(r_j\) 改为 \(p-1\)，然后加入 \(（i,p,n）\)。

代码可以看例题 P1912。

满足四边形不等式的函数类

性质一： 若函数 \(w_1(i,j)\) 和 \(w_2(i,j)\) 满足四边形不等式（或区间单调性），那么对于任意的 \(c_1 \leq 0 ,c_2 \leq 0\)，函数 \(c_1 w_1(i,j)+c_2 w_2(i,j)\) 满足四边形不等式（或区间单调性）。

性质二： 若存在函数 \(f(x)\) 和 \(g(x)\)，\(w(i,j)=f(i)-g(j)\)，则 \(w(i,j)\) 满足四边形恒等式。当 \(f\) 和 \(g\) 单调增加时，则 \(w\) 还满足区间包含单调性。

性质三： 设 \(f(x)\) 是一个单调增加的下凸函数，若函数 \(w(i,j)\) 满足四边形不等式和区间包含单调性，则复合函数 \(f(w(i,j))\) 也满足四边形不等式和区间包含单调性。

性质四： 设 \(f(x)\) 是一个下凸函数，若函数 \(w(i,j)\) 满足四边形不等式和区间包含单调性，则复合函数 \(f(w(i,j))\) 也满足四边形不等式。

例题

P1912 [NOI2009] 诗人小G

\[f_{i}=\min_{j<i}(f_{j}+w_{j+1,i}) (1 \leq i \leq n) \]

\(w_{j,i}=|s_i-s_j-L|^p\)

如何证明 \(w\) 满足四边形不等式

外层外层函数 \(y=|x|^p (x>0)\) 为下凸函数；内层函数 \(w_1(i,j)=len_i-len_j-L\) 满足四边形不等式且满足区间包含单调性，所以 \(w\) 满足四边形不等式。

这种形式只能用二分队列（反正我只会这个），注意会爆 long long ，所以用 long double 存。

点击查看代码 
#include<bits/stdc++.h>
#define int long long
#define LD long double
using namespace std;
const int N=1e5+10;
const int inf=1e18;
char a[N][40];
LD mgml(LD x,int p){
    LD ans=1;
    while(p){
        if(p&1) ans=ans*x;
        x=x*x;
        p>>=1;
    }
    return ans;
}
int n,L,p;
int s[N];
LD val(int x,int y){
    return mgml(abs(s[y]-s[x]-L+y-x-1),p);
}
int r[N],l[N];
int q[N],head,tail;
LD f[N];
int las[N];
int st[N],top=0;
signed main(){
    int T;
    scanf("%lld",&T);
    while(T--){
        memset(f,127,sizeof(f));
        memset(las,0,sizeof(las));
        memset(st,0,sizeof(st));
        scanf("%lld%lld%lld",&n,&L,&p);
        s[0]=0;
        for(int i=1;i<=n;i++){
            scanf("%s",a[i]+1);
            s[i]=s[i-1]+strlen(a[i]+1);
        }
        head=1,tail=0;
        f[0]=0;
        q[++tail]=0;
        l[0]=1,r[0]=n;
        for(int i=1;i<=n;i++){
            while(head<=tail && r[q[head]]<i) head++;
            las[i]=q[head];
            f[i]=f[q[head]]+val(q[head],i);
            while(head<=tail &&f[i]+val(i,l[q[tail]]) < f[q[tail]]+val(q[tail],l[q[tail]])) tail--;
            if(head>tail){
                q[++tail]=i;
                l[i]=i+1,r[i]=n;
            }           
            else if(f[i]+val(i,r[q[tail]]) > f[q[tail]]+val(q[tail],r[q[tail]])){
                if(r[q[tail]]<n){
                    l[i]=r[q[tail]]+1;
                    r[i]=n;
                    q[++tail]=i;
                }
            }
            else{
                int ls=l[q[tail]],rs=r[q[tail]];
                int pos=0;
                while(ls<=rs){
                    int mid=(ls+rs)/2;
                    if(f[i]+val(i,mid) <= f[q[tail]]+val(q[tail],mid)){
                        pos=mid;
                        rs=mid-1;
                    }
                    else ls=mid+1;
                }
                r[q[tail]]=pos-1;
                if(l[q[tail]]>l[q[tail]]) tail--;
                q[++tail]=i;
                l[i]=pos;
                r[i]=n;
            }
        }
        if(f[n]>inf) printf("Too hard to arrange\n");
        else{
            printf("%.0Lf\n",f[n]);
            int tmp=n;
            top=0;
            while(tmp){
                st[++top]=tmp;
                tmp=las[tmp];
            }
            for(int i=top;i>=1;i--){
                for(int j=st[i+1]+1;j<=st[i];j++){
                    cout<<a[j]+1;
                    if(j!=st[i]) cout<<" ";
                }
                printf("\n");
            }
        }
        printf("--------------------\n");
    }
}

锯木厂选址

转移形式与问题 \((1)\) 类似，所以直接分治求解就可以。