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

TallBanana · 2024-05-29 20:43:24 · 算法·理论

四边形不等式

1.四边形不等式

对于 a\le b\le c\le d 和定义域为整数域的二元函数 w，若有

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

则称 w 满足四边形不等式

2.拓展形式

对于 a\le b 和定义域为整数域的二元函数 w，若有

w(a,b+1)+w(a+1,b)\ge w(a,b)+w(a+1,b+1)

则称 w 满足四边形不等式

3.区间包含单调性

对于 a\le b\le c\le d 和定义域为整数域的二元函数 w，若有

w(a,d)\ge w(b,c)

则称 w 满足区间包含单调性

4.性质

性质1：若函数 w_1(l,r),w_2(l,r) 均满足四边形不等式（或区间包含单调性），则对于任意 c_1,c_2\ge0，函数 c_1w_1+c_2w_2 也满足四边形不等式（或区间包含单调性）。
性质2：若存在函数 f(x),g(x) 使得 w(l,r)=f(r)-g(l)，则函数 w 满足四边形不等式。当 f,g 单调增加时，函数 w 还满足区间包含单调性。
性质3：设 h(x) 为一单调增加的下凸函数，若函数 w(l,r) 满足四边形不等式且满足区间包含单调性，则复合函数 h(w(l,r)) 也满足四边形不等式和区间包含单调性。
性质4：设 h(x) 为一下凸函数，若函数 w(l,r) 满足四边形不等式且满足区间包含单调性，则复合函数 h(w(l,r)) 也满足四边形不等式。

这里不给出证明。

模板

形式1

求 f_i=\min\ w(j,i)\ \ \ (1\le j\le i\le n)

这里以及下文都假定成本 w(j,i) 可以在 O(1) 时间内计算

默认从1开始编号

code1

typedef long long LL;
LL n,f[N];
LL w(LL j,LL i) { return ...; }//区间j->i的成本
void DP(LL l,LL r,LL k_l,LL k_r)
{
    if(l>r) return;
    LL mid=l+r>>1,k=k_l;
    for(int i=k_l;i<=min(k_r,mid);i++)
        if(w(i,mid)<w(k,mid)) k=i;
    f[mid]=w(k,mid);
    DP(l,mid-1,k_l,k);
    DP(mid+1,r,k,k_r);
}

形式2

求 f_i=\min\ f_j+w(j+1,i)\ \ \ (0\le j<i\le n)

code2

typedef long long LL;
LL n,L,c[N],f[N],q[N],hh,tt,rt[N],lt[N];
LL w(LL i,LL j) { return .../*区间j+1->i的成本*/+f[j]; }
void solve()
{
    q[0]=0;
    lt[0]=1;
    rt[0]=n;
    for(int i=1;i<=n;i++)
    {
        while(hh<=tt&&rt[q[hh]]<i) hh++;
        lt[q[hh]]=i;
        f[i]=w(i,q[hh]);
        while(hh<=tt&&w(lt[q[tt]],i)<w(lt[q[tt]],q[tt])) tt--;
        if(hh>tt)
        {
            q[++tt]=i;
            lt[i]=i+1;
            rt[i]=n;
        }
        else if(w(rt[q[tt]],q[tt])<w(rt[q[tt]],i))
        {
            if(rt[q[tt]]<n)
            {
                q[++tt]=i;
                lt[i]=rt[q[tt-1]]+1;
                rt[i]=n;
            }
        }
        else
        {
            LL l=lt[q[tt]],r=rt[q[tt]],mid;
            while(l+1<r)
            {
                mid=l+r>>1;
                if(w(mid,i)<w(mid,q[tt])) r=mid;
                else l=mid;
            }
            rt[q[tt]]=l;
            q[++tt]=i;
            lt[i]=r;
            rt[i]=n;
        }
    }
}

形式3

求 f(k,i)=\min\ f(k-1,j-1)+w(j,i)\ \ \ (1\le k \le m,1\le i \le n)

code3

typedef long long LL;
LL w(LL i,LL j) { return .../*区间i->j的成本*/; }
void solve()
{
    for(int i=1;i<=n;i++)
    {
        f[1][i]=w(1,i);
        opt[1][i]=1;
    }
    for(int i=2;i<=k;i++)
    {
        for(int j=n;j>=i;j--)
        {
            LL s=opt[i-1][j],t=opt[i][j+1],res=s;
            if(j==n) t=n;
            for(int o=s+1;o<=t;o++)
                if(f[i-1][o-1]+w(o,j)<f[i-1][res-1]+w(res,j))
                    res=o;
            f[i][j]=f[i-1][res-1]+w(res,j);
            opt[i][j]=res;
        }
    }
    printf("%lld",f[k][n]);
}

形式4

求 f(i,j)=\min f(i,k)+f(k+1,j)+w(i,j)\ \ \ (1\le i \le j \le n,i\le k<j)

code4

typedef long long LL;
LL n,f[N][N],opt[N][N];
LL w(LL i,LL j) { return ...; }//区间i->j的成本
void solve()
{
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            f[i][j]=1e18;
    for(int i=1;i<=n;i++)
    {
        f[i][i]=0;
        opt[i][i]=i;
    }
    for(int len=2;len<=n;len++)
        for(int i=1;i<=n-len+1;i++)
        {
            int j=i+len-1;
            for(int o=opt[i][j-1];o<=opt[i+1][j];o++)
                if(f[i][j]>f[i][o]+f[o+1][j]+w(i,j))
                {
                    f[i][j]=f[i][o]+f[o+1][j]+w(i,j);
                    opt[i][j]=o;
                }
        }
}