标签：不等式 int leq 满足四边形单调

四边形不等式

对于任意的 $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)$ 类似，所以直接分治求解就可以。

参考资料

标签：不等式,int,leq,满足,四边形,单调
From： https://www.cnblogs.com/jinjiaqioi/p/17913146.html

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