四边形不等式

对于一个代价函数 $w(l,r)$，如果对于任意的 $a\le b\le c\le d$，都满足：

则称 $w$ 满足四边形不等式。俗称“交叉小于包含”。

证明 $w$ 满足四边形不等式，等价于证明 $w$ 满足：

感性理解即可，这个东西叫 Monge 矩阵。

决策单调性

对于一个 DP 转移方程：

其中 $w$ 满足四边形不等式，则 $f$ 满足决策单调性，即：

令 $f_i$ 的最优决策点为 $p_i$（即 $f_{i}$ 由 $j=p_i$ 转移得到），那么对于任意的 $i’\lt i$，都有 $p_{i’}\le p_i$。

可以用反证法证明一下。如果存在 $i_2\lt i_1$，使得 $j_2=p_{i_2}\gt j_1=p_{i_1}$（对于 $i$，$j_1$ 严格优于 $j_2$），也就是如下关系：

此时 $j_1\lt j_2\lt i_2\lt i_1$。那么根据四边形不等式和最优决策点两个性质，可以推出以下三个式子：

分别移项得：

合并一下就推出 $f_{j_1}-f_{j_2}\lt f_{j_1}-f_{j_2}$，显然是不对的，所以假设不成立，原命题得证。

四边形不等式优化 DP

模板题

首先我们可以写出最朴素的 DP，定义 $f_{k,i}$ 表示前 $i$ 个人分 $k$ 段的总代价的最小值，则有如下转移：

其中 $w(j,i)$ 表示将区间 $(j,i]$ 中的人分成一段的代价，显然可以用 $a$ 的二维前缀数组 $s$ 表示：

$w$ 是满足四边形不等式的：一大段人分成一段，肯定不如拆成两段，进而推得四边形不等式。

因此 $f_k$ 具有决策单调性。

这有什么用呢？这显然有用。我们可以在转移过程中用双端队列维护每个位置的最优决策点 $j$，最优决策点相同的位置合并成一个区间 $[l,r]$ 塞进队列，大概如下：

对于 $i$，我们可以从队头取出其对应的最优决策点，计算答案。然后更新后面的最优决策点，具体过程如下：

因为有决策单调性，所以目前以 $i$ 为最优决策点的位置一定是序列的一个后缀。我们每次从队尾取出一个区间 $[l,r]$，其原最优决策点为 $j$，如果现在 $i$ 转移到 $l$ 优于 $j$ 转移到 $l$，则将这段出队；否则，有可能这段里的某个后缀的最优决策点均为 $i$，我们需要二分出分界点 $x$，满足 $[l,x)$ 的最优决策点为 $j$，$[x,r]$ 的最优决策点为 $i$，然后将新的段放入队列，停止循环。

using vi=vector<int>;

vector<vi>f(m+1,vi(n+1));
struct S{int l,r,j;};
deque<S>q;
q.eb(S{1,n,0});
auto W=[&](int j,int i){return (s[i][i]-s[i][j]-s[j][i]+s[j][j])/2;};
auto func=[&](int k,int i,int j){return f[k][j]+W(j,i);};
for(int k=1;k<=m;k++){
    deque<S>q2;
    q2.eb(S{1,n,0});
    for(int i=1;i<=n;i++){
        while(!q.empty()&&q.front().r<i)q.pop_front();
        assert(!q.empty());
        f[k][i]=func(k-1,i,q.front().j);
        while(!q2.empty()&&func(k,q2.back().l,q2.back().j)>=func(k,q2.back().l,i))q2.pop_back();
        int sc=i+1;
        if(!q2.empty()){
            S nd=q2.back();q2.pop_back();
            int l=nd.l,r=nd.r,mid;//二分分界点
            sc=r+1;
            while(l<=r){
                mid=(l+r)/2;
                if(func(k,mid,nd.j)>=func(k,mid,i))r=mid-1,sc=mid;
                else l=mid+1;
            }
            if(sc!=nd.l)q2.eb(S{nd.l,sc-1,nd.j});
        }
        if(sc!=n+1)q2.eb(S{sc,n,i});
    }
    q=q2;
}
cout<<f[m][n]<<endl;

using vi=vector<int>;

vector<vi>f(m+1,vi(n+1));
struct S{int l,r,j;};
deque<S>q;
q.eb(S{1,n,0});
auto W=[&](int j,int i){return (s[i][i]-s[i][j]-s[j][i]+s[j][j])/2;};
auto func=[&](int k,int i,int j){return f[k][j]+W(j,i);};
for(int k=1;k<=m;k++){
    deque<S>q2;
    q2.eb(S{1,n,0});
    for(int i=1;i<=n;i++){
        while(!q.empty()&&q.front().r<i)q.pop_front();
        assert(!q.empty());
        f[k][i]=func(k-1,i,q.front().j);
        while(!q2.empty()&&func(k,q2.back().l,q2.back().j)>=func(k,q2.back().l,i))q2.pop_back();
        int sc=i+1;
        if(!q2.empty()){
            S nd=q2.back();q2.pop_back();
            int l=nd.l,r=nd.r,mid;//二分分界点
            sc=r+1;
            while(l<=r){
                mid=(l+r)/2;
                if(func(k,mid,nd.j)>=func(k,mid,i))r=mid-1,sc=mid;
                else l=mid+1;
            }
            if(sc!=nd.l)q2.eb(S{nd.l,sc-1,nd.j});
        }
        if(sc!=n+1)q2.eb(S{sc,n,i});
    }
    q=q2;
}
cout<<f[m][n]<<endl;

模板题2

依旧先写出最朴素的 DP，设 $f_i$ 表示只考虑前 $i$ 句的最小代价，则有如下转移：

其中 $w(j,i)$ 可以用句子长度的前缀和 $s_i=\sum_{k=1}^{i}\text{len}_k$ 表示：

感性理解一下这玩意儿满足四边形不等式即可（其实是我还没学会怎么证），后面的就跟上一题一样了。