四边形不等式优化DP

1.概念

四边形不等式是对一个二元函数定义：$w(l,r)$。这里的$w(l,r)$可以看作价值，权值或着价格都可以。

对于任意$a\le b\le c\le d$ ，若都有$w(a,d)+w(b,c)\ge w(a,c)+w(b,d)$，我们就称$w(l,r)$满足四边形不等式，可以简单记为：”交叉小于包含“。

同时有结论，对于$a\le b$，有$w(a,b-1)+w(a+1,b)\le w(a,b)+w(a+1,b-1)$。

结论：若两个函数之间满足四边形不等式，那么和也满足四边形不等式。

话说为啥叫四边形不等式：

$AD+BC\ge AC+BD$，这个显然在初中是学过的。

反四边形不等式：

就是符号调换一下：$w(a,d)+w(b,c)\le w(a,c)+w(b,d)$

2. 1D/1D优化

这里不是2.1

特征转移方程：

$$f(i)=\min_{1\le j < i} f(j)+w(i,j)$$

如果$w$满足四边形不等式的话，我们就可以进行决策单调性优化。

$$f(i)=\max_{1\le j < i} f(j)+w(i,j)$$

如果$w$满足反四边形不等式，我们也可以进行决策单调性优化。

啥是决策单调性？

2.1 决策单调性

这个我们要好好说一说。

我们记$p_i$表示对于$i$而言，枚举的$j$使得$f(j)+w(i,j)$最小的值，说人话就是$f(i)$从哪个$j$对应的值转移过来的。如果$p$在$[1,n]$ 上单调不见，那么我们就称$f$有决策单调性。

如果$f(i)=\min_{1\le j < i} f(j)+w(i,j)$中$w$满足四边形不等式，那么$f$有决策单调性。

[!TIPS]
这个条件是充分条件，反过来不一定成立！

同理，如果$f(i)=\max_{1\le j < i} f(j)+w(i,j)$，其中$w$满足反四边形不等式，那么$f$同样也有决策单调性。

那为什么叫决策单调性？其实四边形不等式你看着简单，实际上后面蕴含这导数和混合偏导数的关系，这里我不作解释，感兴趣去往上搜搜。

接下来我们说明的是四边形不等式，反四边形不等式与下面的完全相反，包括图形
事实上，当我们$x$越来越大的时候，$w'$即$w$的导数也越来越小。图像呈下面的样子。

当导数逐渐减少的时候，图形的斜率减少趋0，图像越来越平，获得的决策点$p_i$也越来越往后，也就是下图：

结论：

对于$f(i)=\min_{1\le j < i} f(j)+w(i,j)$，需要$w(i,j)$满足四边形不等式。
对于$f(i)=\max_{1\le j < i} f(j)+w(i,j)$，需要$w(i,j)$满足反四边形不等式。

根据图像也不难发现，$p_{i-1}\le p_{i}\le p_{i+1}$，这就是决策单调性。

2.2 单调队列+二分维护

若转移方程是$f_{j} +w \rightarrow f_i$，前推后，那么我们称这个问题叫在线问题我们可以用单调队列+二分的思想。

观察图形，发现类易于一个凸壳的性质，我们可以类似于斜率优化一样来维护这个凸壳。但是有一个问题？这个是曲线又不是直线，不能判断斜率，怎么做？也就是不能简单地用队头队尾$O(1)$维护分界点，这个时候只能每次扫一遍凸壳确定。也就是二分。

1. 检查队头，设队头为$(j_0,l_0,r_0)$，若$r_0=i-1$，删除队头否则令$l_0=i$。
2. 取队头决策，计算$f[i]$。
3. 尝试插入$i$。
   • 取出队尾，记为$(j_t,l_t,r_t)$。
   • 若对于$f[l_i]$来说，$i$比$j_t$更优，即$f[i]+val(i,l_{t)} \le f[j_t]+val(j_t,l_t)$，记$pos=l_t$，删除队尾，回到取出队尾的步骤。
   • 若对于$f[r_i]$来说，$i$比$j_t$更优，即$f[i]+val(i,r_{t)} \le f[j_t]+val(j_t,r_t)$，记$pos=l_t$，直接插入$(i,pos,n)$即可
   • 否则，在$[l_t,r_t]$上二分，求出位置$pos$，在此之前决策$j_t$更优，后面$i$更优，让后令队尾的$r_t=pos$，插入$(i,pos,n)$即可。

代码如下：

void insert(int x){
    int pos=n+1;
    while(ql<=qr&&f[x]+w(x,q[qr].l)<=f[q[qr].j]+w(q[qr].j,q[qr].l)) pos=q[qr--].l;
    if(ql<=qr&&f[x]+w(x,q[qr].r)<=f[q[qr].j]+w(q[qr].j,q[qr].r)){
        int l=q[qr].l,r=q[qr].r;
        while(l+1<r){
            int mid=(l+r)>>1;
            if(f[x]+w(x,mid)<=f[q[qr].j]+w(q[qr].j,mid)) r=mid;
            else l=mid;
        }
        q[qr].r=r-1;
        pos=r;
    }
    if(pos!=n+1){
        q[++qr]={pos,n,x};
    }
}

DP的时候正常取决策即可：

ql=1,qr=0;
q[++qr]={1,n,0};
for(int i=1;i<=n;i++){
    while(ql<=qr&&q[ql].r<i) ql++;
    f[i]=f[q[ql].j]+w(q[ql].j,i);
    ans[i]=ans[q[ql].j]+1;
    insert(i);
}

2.3 分治法

若转移方程是$g+w \rightarrow f$的转移，也就是说转移是由一个已知的函数或这$f$的上一层转移过来，那么我们就可以用分治的方法，这种决策是离线的，我们不依赖$f_{i-1}$来计算$f_i$，这时候就不必采用单调队列这种顺序计算$f_i$了，只需要分治就可以，编码更简单也更灵活。

算法步骤：

1. 初始化：首先暴力遍历$j\in[1,n/2)$来计算$p_{n/2}$，作为分治的中心点。
2. 分治求解：接下来分别计算2个区间$[1,n/2)$和$(n/2,2]$的$p_i$。
   • 对于前半段，最优决策点一定在$[1,p_{n/2}]$之间。
   • 对于后半段，最优决策点一定在$[p_{n/2},p_n]$之间。
3. 递归处理即可。

代码实现如下：

int clac(int i,int j); //计算选择决策j的费用
// l,r是决策区间，kl,kr是决策点的区间
void dfs(int l,int r,int kl,int kr){
	int mid=(l+r)>>1,k=kl;
	for(int i=kl;i<=min(kr,mid-1);i++){
		//求费用最少的f[mid]最优决策点
		if(clac(mid,i)<clac(mid,k)) k=i;
		f[mid]=clac(mid,k);
	}
	if(l<mid) dfs(l,mid-1,kl,k);
	if(r>mid) dfs(mid+1,r,k,kr);
}

//ans=f[n];

复杂度分析：

递归树深度$\log n$，递归执行一个元素至多被扫2次，时间复杂度即为$O(n\log n)$。
空间复杂度显然$O(\log n)$。

分治法的优点：

如果$w(i,j)$不能$O(1)$计算但是可以从$w(i\pm 1,j\pm 1)$来$O(1)$递推，此时分治法就能够以均摊$O(1)$的速度来计算，因为在暴力遍历循环中$w(i,j)$的区间是顺序扩大的，而单调队列计算$w(i,j)$是乱跳的。下面会有例题来解释。

2.4 决策单调性1D1D例题

1.[单调队列二分] P1912 诗人小G

一首诗包含了若干个句子，对于一些连续的短句，可以将它们用空格隔开并放在一行中，注意一行中可以放的句子数目是没有限制的。小 G 给每首诗定义了一个行标准长度（行的长度为一行中符号的总个数），他希望排版后每行的长度都和行标准长度相差不远。显然排版时，不应改变原有的句子顺序，并且小 G 不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下，小 G 对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的$P$ 次方，而一个排版的不协调度为所有行不协调度的总和。
小 G 最近又作了几首诗，现在请你对这首诗进行排版，使得排版后的诗尽量协调（即不协调度尽量小），并把排版的结果告诉他。
给定诗句数$n$，行标准长度$L$与题目描述的$P$，如果不协调度大于$10^{18}$输出"Too hard to arrange"。

不妨设$f[i]$为前$i$个句子的最小不协调度，记长度为$a_i$，$sum_i$为$a_i$的前缀和，不难有转移方程：

$$f[i]=\min_{j=0}^{i-1}f[j]+|sum[i]-sum[j]+(i-j-1)-L|^P$$

就是将$[j+1,i]$作为最后一行，前面照常排。

这里$P$不固定不能考虑斜率优化，考虑四边形不等式，这个证明起来比较难，实在不行可以打表看看。

故代码如下：

#include<bits/stdc++.h>
#define ld long double
#define ll long long
using namespace std;
const int MN=1e5+15;
struct node{
    int c,l,r;
}q[MN];
int T;
int n,ql,qr,L,P,a[MN],pre[MN];
ld f[MN],s[MN];
string st[MN];
vector<int> ans;

ld qpow(ld a,ll b){
    ld ans=1;
    while (b)
    {
        if(b&1){
            ans*=a;
        }
        b>>=1;
        a*=a;
    }
    return ans;
}

ld clac(int x,int y){
    return f[x]+qpow(fabs(s[y]-s[x]-L-1),P);
}

void insert(int x){
    int pos=n+1;
    while(ql<=qr&&clac(x,q[qr].l)<=clac(q[qr].c,q[qr].l)){
        pos=q[qr--].l;
    }
    if(ql<=qr&&clac(x,q[qr].r)<=clac(q[qr].c,q[qr].r)){
        int l=q[qr].l,r=q[qr].r;
        while(l+1<r){
            int mid=l+r>>1;
            if(clac(x,mid)<=clac(q[qr].c,mid)) r=mid;
            else l=mid;
        }
        q[qr].r=r-1;
        pos=r;
    }
    if(pos!=n+1){
        q[++qr]={x,pos,n};
    }
}

void solve(){
    ans.clear();
    memset(f,0,sizeof(f));
    memset(s,0,sizeof(s));
    memset(pre,0,sizeof(pre));
    cin>>n>>L>>P;
    for(int i=1;i<=n;i++){
        cin>>st[i];
        s[i]=s[i-1]+st[i].length()+1;
    }
    ql=1,qr=0;
    q[++qr]={0,1,n};
    for(int i=1;i<=n;i++){
        while(ql<=qr&&q[ql].r<i) ql++;
        f[i]=clac(q[ql].c,i);
        pre[i]=q[ql].c;
        insert(i);
    }
    if(f[n]>1e18){
        cout<<"Too hard to arrange\n";
    }else{
        cout<<(ll)f[n]<<'\n';
        for(int i=n;i;i=pre[i]){
            ans.push_back(i);
        }
        int cur=ans.size()-1,tmp=0;
        for(int i=1;i<=n;i++){
            if(tmp) cout<<" ";
            cout<<st[i];
            if(i==ans[cur]) cout<<'\n',cur--,tmp=0;
            else tmp++;
        }
    }
    cout<<"--------------------\n";
}

int main(){
    cin>>T;
    while (T--)
    {
        solve();
    }
    
    return 0;
}

2.[分治法] CF868F Yet Another Minimization Problem

给定一个长度为$n$的序列$a$，要把它分成$k$ 个子段。每个子段的费用是其中相同元素的对数。求所有子段的费用之和的最小值。
$2\le n\le 10^5,2\le k\le min(n,20),1\le a_{i}\le n$

不难设转移方程，$f[i][j]$表示执行到第$i$个数，共化了$j$个子段，不难有转移方程。

$$f[i][j]=\min_{k=1}^{i-1}f[k][j-1]+w(k+1,i)$$

时间复杂度为$O(n^2)$，不可承受，况且$w$的计算又是一个头痛的地方。

考虑$w$能否满足四边形不等式，不难发现$i$向右移动时$w$单调不减，所以肯定满足决策单调性。

考虑决策单调性，不难发现这个不用顺序计算，考虑分治法，但是这样算不太好，我们把方程两维转换一下。

$f[i][j]$表示共化了$i$个段，执行到第$j$个数，转移方程类似。

这样就能分治了，其实也可以不换（雾）。

考虑$w$如何快速的计算，区间相同元素，区间颜色段问题，这不是莫队的拿手好戏吗。我们做一个类似莫队的暴力，这样，用左右指针进行区间移动，考虑一次最多移动多少次？从$[l,r]$移动到最后一次的$[l,mid]$最多移动$r-l$次，同一层最多$O(n)$次，所以均摊单次计算$O(1)$，时间复杂度$O(kn\log n)$。

其实这里$w$的计算也和上面分治法的优点对应，我们的$w(i\pm 1,j\pm 1)$可以通过$O(1)$移动指针$O(1)$算出来，但是如果我们使用单调队列的话就不能利用这个性质了。

故代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr int MN=1e5+15;
int n,mk,a[MN],cnt[MN],wl=1,wr;
ll f[MN][2],now,pre=1,w;

inline ll cost(int l, int r) {
    while (wl > l) wl--, w += cnt[a[wl]]++;
    while (wr < r) wr++, w += cnt[a[wr]]++;
    while (wl < l) w -= --cnt[a[wl]], wl++;
    while (wr > r) w -= --cnt[a[wr]], wr--;
    return w;
}
inline ll clac(int i, int j) {
    return f[j][pre] + cost(j+1, i);
}

void dfs(int l,int r,int kl,int kr){
    int mid=(l+r)>>1,k=kl;
    ll kv=clac(mid,k);
    for(int i=kl;i<=min(kr,mid);i++){
        ll tmp=clac(mid,i);
        if(tmp<kv){
            k=i;
            kv=tmp;
        }
    }
    f[mid][now]=kv;
    if(mid>l) dfs(l,mid-1,kl,k);
    if(mid<r) dfs(mid+1,r,k,kr);
}

int main(){
    cin>>n>>mk;
    wr=n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        f[i][now]=(w+=cnt[a[i]]++);
    }
    for(int i=2;i<=mk;i++){
        swap(now,pre);
        dfs(1,n,1,n);
    }
    cout<<f[n][now];
    return 0;
}

3. 2D/1D优化

3.1 区间决策点单调性

这里和上面的单点决策单调性就没太大关系了，我们这里是区间决策单调性。

这里2D表示我们的状态维度是二维，而决策点是一维的。

特征方程：

$$\begin{aligned} f[i][j]& =\min_{k=i}^{j-1}(f[i][k]+f[k+1][j]+w[i][j])\newline & = \min_{k=i}^{j-1}(f[i][k]+f[k+1][j])+w[i][j] \end{aligned}$$

你会说，这不就是区间DP吗？

是…也不是？

但是这里我们的$w(i,j)$不仅要满足四边形不等式，更要满足单调性。

即：

$$\text{对于任意}a\le b\le c\le d,w(a,d)\ge w(b,c )\text{ 或 }w(i+1,j) \le w(i,j+1)$$

速记：小区间$\le$大区间。

如果$w(i,j)$满足四边形不等式和单调性，那么我们用$dp$计算的时间复杂度是$O(n^2)$。

引理1：如果$w(i,j)$满足四边形不等式和单调性，则$f[i][j]=\min_{k=i}^{j-1}(f[i][k]+f[k+1][j]+w[i][j])$也满足四边形不等式。

引理2：记$s[i][j]=k$为$f[i][j]$取得最小值的$k$，如果$f[i][j]$满足四边形不等式，有：

$$s[i][j-1]\le k\le s[i+1][j]$$

速记：左中区间$\le$ 大区间$\le$ 右中区间。

---

对于求最大值：

$$\begin{aligned} f[i][j]& =\max_{k=i}^{j-1}(f[i][k]+f[k+1][j]+w[i][j])\newline & = \max_{k=i}^{j-1}(f[i][k]+f[k+1][j])+w[i][j] \end{aligned}$$

需要满足反四边形不等式与最大值的单调性。

单调性即：

$$\text{对于任意}a\le b\le c\le d,w(a,d)\le w(b,c )$$

速记：小区间$\ge$大区间。反过来即可。

如果$w(i,j)$满足反四边形不等式和单调性，那么我们用$dp$计算的时间复杂度是$O(n^2)$。

引理3：如果$w(i,j)$满足反四边形不等式和单调性，则$f[i][j]=\max_{k=i}^{j-1}(f[i][k]+f[k+1][j]+w[i][j])$也满足反四边形不等式。

引理4：记$s[i][j]=k$为$f[i][j]$取得最大值的$k$，如果$f[i][j]$满足四边形不等式，有：

$$s[i][j-1]\le k\le s[i+1][j]$$

速记：左中区间$\le$ 大区间$\le$ 右中区间。这个是一样的。

3.2 区间决策点单调性模板题

石子合并，只求最小，有环，但$n\le 5000$，喜欢我$O(n^2)$吗？

不难发现这个转移方程是很明显满足四边形不等式的，毕竟本身就有单调性。

所以怎么实现呢，根据上面的引理，我们只需要在$[s[i][j-1],s[i+1][j]]$这个区间内进行遍历即可，顺便记录一下决策点，这个可比1D/1D好写多了，只需要开个数组记录就可以。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int MN=5125,INF=1e9;
int f[MN][MN],p[MN][MN],n,s[MN];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]+=s[i-1];
        p[i][i]=i;
    }
    for(int len=2;len<=n;len++){
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            f[l][r]=INF;
            for(int k=p[l][r-1];k<=p[l+1][r];k++){
                int t=f[l][k]+f[k+1][r]+s[r]-s[l-1];
                if(f[l][r]>t){
                    f[l][r]=t;
                    p[l][r]=k;
                }
            }
        }

    }
    cout<<f[1][n];
    return 0;
}

为啥没说最大值，最大值不满足最大值的单调性，所以不行只能$O(n^3)$。

4.写在最后

感谢阅读！

本文章素材来源：

1. 算法竞赛进阶指南
2. しずり雪 の Blog，大佬图太好了！
3. 洛谷日报，但是不知道哪篇www