决策单调性 & 四边形不等式

_XHY20180718_ · 2024-01-17 21:15:52 · 算法·理论

决策单调性是个非常有用的东西，他的优化功能甚至超出了 dp 的范围。

对于一个形如以下的 DP 式子：

f_i=\min_{j=1}^{i-1}w_{j,i}

若有对于 \forall a\leq b\leq c\leq d，满足 w_{a,c}+w_{b,d}\leq w_{a,d}+w_{b,c} 的四边形不等式性质。

那么 f_i 必定满足决策单调性：

对于 \forall f_i，若 f_i=f_{p_i}+w_{p_i,i}（即 f_i 是由 f_{p_i} 转移过来的），则 \forall j>i,f_j\not=f_k+w_{k,j}(k<p_i)，即 f_j 不可能由 f_k(k<p_i) 转移过来，一定是通过 p_i 或之后的状态转移过来的。

下面是证明：

设 p_i 为 i 的最优决策点，则：

f_{p_i}+w_{p_i,i}\leq f_k+w_{k,i}(k<p_i)

对于 \forall k<p_i<i<j，根据四边形不等式，有：

w_{k,i}+w_{p_i,j}\leq w_{k,j}+w_{p_i,i}

又因为：

f_{p_i}+w_{p_i,i}\leq f_k+w_{k,i}(k<p_i)

所以有：

f_{p_i}+w_{p_i,j}\leq f_k+w_{k,j}

这表明通过 f_k 来转移 f_j 一定比通过 f_{p_i} 来转移 f_j 更劣，证毕。

反过来也是一样的，反四边形不等式在 f_i=\max_{j=1}^{i-1}f_j+w_{j,i} 的时候同样满足决策单调性。

接下来看看应用：

P1912 [NOI2009]诗人小G。

首先容易列出转移方程：设 s_i 为第 i 个诗句以及之前的诗句长度前缀和， f_i 为考虑到第 i 个句子的最小不和谐度。

f_i=min_{j=1}^{i-1}(f_j+abs(s_i-s_{j-1}-L)^P)

容易看出四边形不等式。

一般来说，一个满足四边形不等式的 dp 式子，有两张算法优化：

分治：

这种方法一般要让 w_{j,i} 与 f_j 无关。

由于 w_{j,i} 与 f_j 通常有关系，所以一般只在二维状态时用到。

原理就是先求出 [1,n] 的决策单调性区间 [p_1,p_n]，然后再一步步分治：

inline long double calc(int j,int i);
void solve(int x,int y,int l,int r){
    if(l>r)return;
    int mid=l+(r-l>>1),z=x;
    for(int i=x; i<=min(mid-1,y); ++i){
        if(calc(i,mid)<calc(z,mid))z=i;
    }f[mid]=calc(z,mid);lst[mid]=z;
    solve(z,y,mid+1,r);
    solve(x,z,l,mid-1);
}

接下来讲第二种方法：

三元组+双端队列:

我们一步步考虑可能的决策点 i，从 1 枚举到 n。

定义一个三元组：(p,l,r)，表示对于我们当前考虑到的所有可能的决策点 (1\sim i)，[l,r] 这段区间的最有决策点均为 p。

即在所有当前考虑到的可能的决策点中 (1\sim i)，f_{l\sim r} 的当前最优决策点为 p，由 f_p 转移过来。

首先初始化，一般是：qu[L=R=1]={0,1,n}。

那么我们枚举决策点时，我们首先一定要先根据之前找到的最优决策点算出 f_i，然后再去找到所有考虑到的决策点中被 f_i 更新之后最优的区间，除非区间不存在，那么这个区间右端点一定是 n，因为 f 满足决策单调性，i 之前的决策点都比 i 要劣，而 i 后面的决策点我们暂时没有考虑到。

怎么对整个序列的三元组们进行更新呢？

我们先把那些区间的左端点的最优决策点都是 i 的区间踢出队尾，接下来就是右端点的最优决策点为 i 的区间（也可能根本没有），那么我们只需要在这个区间上进行二分，找到从左往右第一个点的最优决策点为 i 的点，然后我们把这个区间的右端点设为二分点的上一个点，最后我们再加上二分点到 n 的这个区间即可，决策点为 i。

一般可以这样写：

inline void ins(int x){
    while(L<=R&&calc(x,qu[R].l)<=calc(qu[R].p,qu[R].l))--R;
    if(L<=R&&calc(x,qu[R].r)<=calc(qu[R].p,qu[R].r)){
        int l=qu[R].l,r=qu[R].r,mid,p=qu[R].p;
        while(l<r){
            mid=l+(r-l>>1);
            if(calc(x,mid)<=calc(p,mid))r=mid;
            else l=mid+1;
        }
        qu[R].r=r-1;
    }
    if(qu[R].r<n){
        node t={x,qu[R].r+1,n};
        qu[++R]=t;
    }
}
signed main(){
    qu[L=R=1]={0,1,n};
   for(int i=1; i<=n; ++i){
     f[i]=calc(lst[i]=qu[L].p,i);
     if(qu[L].r==i)++L;
     qu[L].l=i+1;ins(i);
   }
}

P1912 [NOI2009]诗人小G

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
const long double inf=1e18,eps=5;
int T,n,m,Ln,P,a[N],pre[N];
string s[N],ans[N];
int lst[N],L,R;
long double f[N];
struct node{
    int p,l,r;
}qu[N];
inline long double fpm(long double x,int y){
    long double res=1;
    for(;y;y>>=1,x*=x)
        if(y&1)res*=x;
    return res;
}
inline long double calc(int j,int i)
{return f[j]+fpm(abs(pre[i]-pre[j]+i-j-1-Ln),P);}
inline void insert(int x){int pos=n+1;
    while(L<=R&&calc(x,qu[R].l)<=calc(qu[R].p,qu[R].l))pos=qu[R--].l;
    if(L<=R&&calc(x,qu[R].r)<=calc(qu[R].p,qu[R].r)){
        int l=qu[R].l,r=qu[R].r,mid;
        while(l<r){
            mid=l+(r-l>>1);
            if(calc(x,mid)<=calc(qu[R].p,mid))r=mid;
            else l=mid+1;
        }
        qu[R].r=r-1;pos=r;
    }if(pos<=n)qu[++R]={x,pos,n};
}
signed main(){
    cin>>T;while(T--){
        cin>>n>>Ln>>P;
        memset(pre,0,sizeof pre);
        memset(lst,0,sizeof lst);
        for(int i=1; i<=n; ++i)ans[i]="";
        for(int i=1; i<=n; ++i)f[i]=inf+1;
        for(int i=1; i<=n; ++i)
            cin>>s[i],a[i]=s[i].size(),pre[i]=pre[i-1]+a[i];
        qu[L=R=1]={0,1,n};
        for(int i=1; i<=n; ++i){
            f[i]=calc(lst[i]=qu[L].p,i);
            if(qu[L].r==i)++L;
            qu[L].l=i+1;insert(i);
        }
        if(f[n]>=inf+1){cout<<"Too hard to arrange\n";goto A;}
        printf("%.0Lf\n",f[n]);m=1;
        for(int i=n; i; i=lst[i],++m){
            for(int j=lst[i]+1; j<i; ++j)
                ans[m]+=s[j],ans[m]+=' ';
            ans[m]+=s[i];
        }
        for(int i=m-1; i; --i)
            cout<<ans[i]<<'\n';A:;
        cout<<"--------------------\n";
    }
    return 0;
}

[POI2011] Lightning Conductor。

列出式子：

p_i=max_{i=1}^na_j-a_i+\sqrt{|i-j|}

设 w_{j,i}=a_j-a_i+\sqrt{|i-j|} 通过打表得出其 i<j 时满足反四边形不等式，i>j 时满足四边形不等式，分类讨论即可。

直接上分治即可，不过要记得分类讨论，弄两个函数就行了：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
int n,a[N];
long double f[N],g[N];
inline long double calc(int j,int i){return a[j]-a[i]+sqrt(1.0*abs(i-j));}
void solvef(int l,int r,int x,int y){
    if(l>r)return;
    int z=x,mid=l+(r-l>>1);
    for(int i=x+1; i<=min(mid,y); ++i)
        if(calc(i,mid)>=calc(z,mid))z=i;
    f[mid]=calc(z,mid);
    solvef(l,mid-1,x,z);
    solvef(mid+1,r,z,y);
}
void solveg(int l,int r,int x,int y){
    if(l>r)return;
    int z=y,mid=l+(r-l>>1);
    for(int i=y-1; i>=max(mid,x); --i)
        if(calc(i,mid)>=calc(z,mid))z=i;
    g[mid]=calc(z,mid);
    solveg(l,mid-1,x,z);
    solveg(mid+1,r,z,y);
}
signed main(){cin>>n;
    for(int i=1; i<=n; ++i)cin>>a[i];
    solvef(1,n,1,n);solveg(1,n,1,n);
    for(int i=1; i<=n; ++i)
        cout<<(int)ceil(max(f[i],g[i]))<<'\n';
    return 0;
}

再来看一道题：

CF868F:Yet Another Minimization Problem。

老规矩，先列出转移方程：设 calc(l,r) 表示区间 [L,R] 中的元素相同个数。

f_{i,k}=min_{j=1}^{i-1}f_{j,k-1}+calc(j+1,i)

二维转移式子，不是区间 DP 很明显我们可以考虑分治。

但是，上一道题和诗人小 G 我们的贡献都是 O(1) 算的，这里似乎最低也只利用桶来 O(n) 计算？

没有关系，观察分治的过程，我们发现一般情况下左端点只会一个一个动，每次递归时若先递归右区间会移动 \frac{len}{2} 次，而右端点会调到分治的中点，递归进去时肯定是移动 \frac{len}{2} 次(len 指区间长度)，递归出来相当于又重新移动回来了，所以总移动次数肯定也是 O(n) 级别的。

再看看我们本来用桶的计算方式：

把这个区间的数用桶统计完后，每次一个桶内元素的数量增加 1，那么总贡献就会增加这个桶内元素原有的数量，因为新进来的元素与原有的元素都可以构成一个二元组，减少就是做逆运算，同理。

将两个性质结合起来，我们发现桶内元素数量的变化在移动一次端点时可以 O(1) 进行计算，那就好办了，直接 O(n)，过！

最后来讲讲关于区间 dp，的决策单调性，观察我们的转移式：

f_{l,r}=f_{l,k}+f_{k+1,r}+calc(l,r)

区间 dp 转移式比较特殊，他并不是由一个 f 推到另一个 f ，而是由 f_{l,k} 与 f_{k+1,r} 和代价 w_{l,r} 共同组成的 f_{l,r}。

那我们该怎么办呢？

首先 w_{l+1,r-1}\leq w_{l,r}，w 已经满足在长度上单调递增了。

f_{l,r}+f_{l+1,r-1}\leq f_{l,r-1}+f_{l+1,r}

设 f_{l,r} 的决策点为 s_{l,r}

即 f_{l,r}=f_{l,s_{l,r}}+f{s_{l,r}+1,r} 是最优解。

那么一定有：s_{l,r-1}\leq s_{l,r}\leq s_{l+1,r}

所以就可以直接优化了，每次会遍历一个 n\times m 矩阵上的一条对角线，所以复杂度是 O(n(m+n))。

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

为了更方便地证明一个函数满足四边形不等式，我们有以下几条性质：

性质 1：若函数 w_1(j,i) 和 w_2(j,i) 均满足四边形不等式（或区间包含单调性），则对于任意 c_1,c_2\geq 0，函数 c_1w_1+c_2w_2 也满足四边形不等式（或区间包含单调性）。

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

性质 3：设 h(x) 是一个单调增加的凸函数，若函数 w(j,i) 满足四边形不等式并且对区间包含关系具有单调性，则复合函数 h(w(j,i)) 也满足四边形不等式和区间包含单调性。

性质 4：设 h(x) 是一个凸函数，若函数 w(j,i) 满足四边形恒等式并且对区间包含关系具有单调性，则复合函数 h(w(j,i)) 也满足四边形不等式。

首先需要澄清一点，凸函数（Convex Function）的定义在国内教材中有分歧，此处的凸函数指的是下凸函数，即（可微时）一阶导数单调增加的函数。

例题：

P5574 [CmdOI2019] 任务分配问题

P4767 [IOI2000] 邮局加强版