决策单调性

概论

决策单调性优化是一类利用决策单调性排除动态规划过程中冗余计算的优化方式，通常可以用四边形不等式证明

引例1

P1912 [NOI2009]诗人小G

题目大意

给定$n$句诗，$P$与标准行长度$L$，可以将若干句诗摆在一行并用空格(计入长度)隔开，若某一行的长度为$len$，则行不协调度为$|len-L|^P$，求怎样摆放诗句可以使得各行的不协调度的总和最小。$n\leq 10^5$

状态转移方程

重点在于优化动态规划，所以我直接放动态转移方程了

记$a_i$为第$i$句诗的长度，$s_i$为前$i$句诗的总长度加上$i$个空格的长度，即$s_i=i+\sum_{j=1}^{i}a_i$，$L$为标准长度。记$F_i$表示摆放前$i$句诗的最小不协调度，则有$F_i=\min_{0\leq l<i}{\{F_k+|s_i-s_k-L-1|^P\}}$。这个状态转移方程的意思是前$k$句诗按它的最优方案排列，第$k+1$句诗到第$i$句诗另起一行。

显然这个状态转移的时间复杂度是$O(n^2)$的，无法通过本题的数据范围，所以我们考虑优化。

优化——决策单调性

动态规划的优化基本上都是排除冗余的计算，要想优化这个动态规划，我们需要找到合适的性质，并合理利用该性质排除冗余的计算。既然要找性质，那就来打个表找找规律吧,我手造了一组数据并跑了一下，得到如下结果：

观察到，最优值基本上没什么规律，但是最优决策点竟然是单调不递减的！但是，最优决策点单调不递减有什么用呢？

我们记$P_i$为第$i$个位置的最优决策点，显然$P$单调不下降。在我们求出某一个$F_i$的时候，我们要求出仅考虑以$1-i$为决策点的时候，哪一段的最优决策点是$i$。由于决策单调性，我们可以在$P$中找到一个点$j$，对于任意$k<j$有$P_k<i$，对于任意$k\geq j$有$P_k\geq i$。事实上，因为我们仅考虑以$1-i$为决策点，所以我们在计算到$i$时可以认为上面的表述可以转换为”对于任意$k<j$有$P_k<i$，对于任意$k\geq j$有$P_k= i$”，我们可以这么做的原因是在之后的计算中不以$i$为最优决策点的$i’$会被其它的决策点覆盖。关于上面的例子，我绘制了一份$P$的图片，如下图：

所以我们现在的问题转换为：维护一个数组$P$，找到一个点使得这个点之前的$i$都会被其它决策吊打，但在这个点及这个点之后，$i$可以吊打之前的所有决策，并将这个点即后面的所有点的值赋值为$i$

我们先考虑如何找到该点：枚举的复杂度是$O(n)$，但是由于单调性，我们是可以利用二分将复杂度降低至$O(\log n)$的。

接着考虑后一个操作，注意到这是一个区间赋值问题，故我们可以借用类似于珂朵莉树的思想：维护一个队列，队列中的元素为一个三元组$(l,r,x)$表示区间$[l,r]$的值为$x$。于是，在我们计算完$F_i$时，我们从队尾开始检查，如果队尾的三元组$(l_{tail},r_{tail},x_{tail})$的$l_{tail}$取$x_{tail}$不如$i$，那么弹出该三元组，如果$r_{tail}$取$x_{tail}$比$i$好，但是$l_{tail}$取$x_{tail}$比$i$好，此时我们在区间$[l_{tail},r_{tail}]$内二分，找出满足要求的点$mid$，将队尾三元组改为$(l_{tail},mid-1,x_{tail})$，并插入$(mid,n,i)$即可。

那么在开始计算$F_i$时如何找到$P_i$呢？只要我们在开始计算前在队头弹出过时的三元组，即队头的三元组$(l_{head},r_{head},x_{head})$的$r_{head}=i-1$时，我们弹出队头，否则令$l_{head}=i$。那么此时队头就是$P_i$的值了，这个操作是不是让你想起了单调队列？事实上在单调队列优化动态规划中，单调队列维护的是$F_i$，而在这里单调队列维护的是$P_i$，这便是决策单调性的性质带来的好处。另外，在实现中我们没必要真的维护三元组，只需记录每一段区间的最后一个位置与区间的值即可。

什么？你问我复杂度？注意到队列中每一个元素至多被入队出队一次，二分只会做$n$次，所以复杂度应该是$O(n\log n)$的我口胡的。那么本题就完美解决啦不，你会因为字符串等问题调很久的，我说的

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

int getDP(int i,int j){return dp[j]+w(i,j);}
bool check(int now,int x,int y){return getDP(now,x)>=getDP(now,y);}
int getLast(int x,int y){
	int l=x,r=n+1,mid;
    while(l<r){
        mid=(l+r)>>1;
        if(check(mid,x,y)) r=mid;
        else l=mid+1;
    }
    return l;
}
int Work(){
    int head=tail=1,q[MAXN],lst[MAXN];
    q[1]=0;
    for(REG int i=1;i<=n;++i){
        while(head<tail&&lst[head]<=i) ++head;//弹出过时
        dp[i]=getDP(i,q[head]);
        while(head<tail&&lst[tail-1]>=getLast(q[tail],i)) --tail;//弹出无用
        lst[tail]=getLast(q[tail],i),q[++tail]=i;
    }
    return dp[n];
}

正确性？

OIer只需知道结论不需证明，证明是不可能证明的

原来是按照目前大部分BLOG的证明去证明的，但是在我独立证明了引例2的内容后，我发现可以有更能让人听懂的证明

我们可以用反证法，假设$\exists j < i $,$P_j>P_i$，有$P_i<P_j<j<i$

记$w(j,i)=|s_i-s_j-L-1|^P$，因为$P$是最优的，所以我们有：

两式相加，有

因为我们是用反证法，所以只要证明

也就是

我们称该不等式为四边形不等式，特别地，若原状态转移方程是取$\max$，则要将$\geq$改为$\leq$。要想证明这个不等式，先得证明一个定理，这个定理将大大减少证明的难度

• 定理1 若一个定义在整数集上的二元函数$w(x,y)$满足对于任意定义域内的$a<b$，都有$w(a,b+1)+w(a+1,b)\geq w(a,b)+w(a+1,b+1)$成立，则$w(x,y)$满足四边形不等式

要想证明定理1，先证明两个引理

• 引理1 若一个定义在整数集上的二元函数$w(x,y)$满足对于任意定义域内的$a<b$，都有$w(a,b+1)+w(a+1,b)\geq w(a,b)+w(a+1,b+1)$成立，则对任意定义域内的$a< b< c$有$w(a,c+1)+w(b,c)\geq w(a,c)+w(b,c+1)$

• 证明

  • 考虑数学归纳法，若$k$为一非负整数，记$b=a+k$，且$b=a+k<c$

    • 当$k=1$

  • 显然由$a<c$可得

    • $$w(a,c+1)+w(a+1,c)\ge w(a,c)+w(a+1,c+1)$$

    • 即

    • $$w(a,c+1)+w(b,c)\ge w(a,c)+w(b,c+1)$$

    • 当$k>1$

    • 若有

    • $$w(a,c+1)+w(a+k-1,c)\geq w(a,c)+w(a+k-1,c+1)$$

  • 因为$a+k<c$

    • $$w(a+k-1,c+1)+w(a+k,c)\geq w(a+k-1,c)+w(a+k,c+1)$$

    • 两式相加，有

  • $$w(a,c+1)+w(a+k,c)\geq w(a,c)+w(a+k,c+1)$$
    • 也就是$w(a,c+1)+w(b,c)\ge w(a,c)+w(b,c+1)$

  • 证毕

• 引理2 若一个定义在整数集上的二元函数$w(x,y)$满足对于任意定义域内的$a< b< c$有$w(a,c+1)+w(b,c)\geq w(a,c)+w(b,c+1)$，则$w(x,y)$满足四边形不等式

• 证明

  • 若$k$是一个非负整数,记$d=c+k$

    • 当$k=1$

    • 显然由$b<c$有

    • $$w(a,c+1)+w(b,c)\ge w(a,c)+w(b,d)$$

    • 即

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

    • 当$k>1$

    • 假设有

    • $$w(a,c+k-1)+w(b,c)\ge w(a,c)+w(b,c+k-1)$$

    • 因为$c+k>b$

    • $$w(a,c+k)+w(b,c+k-1)\ge w(a,c+k-1)+w(b,c+k)$$

    • 两式相加，有

    • $$w(a,c+k)+w(b,c)\ge w(a,c)+w(b,c+k)$$

    • 即$\forall a<b<c<d,w(a,d)+w(b,c)\ge w(a,c)+w(b,d)$

于是定理1就证明完了

那么，现在只需要证明$w(j,i)=|s_i-s_j-L-1|^P$满足

移项，有

记$u=s_i-s_j-L-1,v=s_i-s_{j+1}-L-1$

只需证$|v|^P-|v+a_{i+1}+1|^P\ge |u|^P-|u+a_{i+1}+1|^P$

因为$u>v$，所以只需证明函数$f(x)=|x|^P-|x+c|^P$($c$为常数)单调不递增即可

可以分类讨论并利用导数解决，此处不赘述

引例2

[POI2011]Lightning Conductor

题目大意

给定一个正整数$n$与非负整数数列$a_n$，对于每一个$i\in [1,n]$，求一个最小的非负整数$p$使得$\forall j\in [1,n],a_j\leq a_i+p-\sqrt{|i-j|}$，$n\leq 5\times 10^5$

伪状态转移方程(大雾

记$i$的答案为$p_i$，移项得$p_i\geq a_j+\sqrt{|i-j|}-a_i$，注意到$p$要最小，所以$p_i=\max_{1\leq j\leq n}{\{a_j+\sqrt{|i-j|}\}}-a_i$。分类讨论一下，记$l_i=\max_{1\leq j\leq i}{\{a_j+\sqrt{i-j}\}}$，$r_i=\max_{i<j\leq n}{\{a_j+\sqrt{j-i}\}}$，显然有$p_i=\max(l_i,r_i)-a_i$。注意到求$r_i$只需将数列颠倒过来按求$l_i$的方法求，所以我们考虑求$l_i$，即求$l_i=\max_{1\leq j\leq i}{\{a_j+\sqrt{i-j}\}}$，时间复杂度$O(n^2)$，仍需优化

优化——决策单调性与证明

手玩一下样例，容易发现这个仍然满足决策单调性。那么我们可以按照上面的方法计算它。但是正确性呢？我们考虑反证法。仍然用$P$表示最优决策

假设$\exists i,j\in [1,n],$$ i < j $,$ P _ j > P _ i $，则有

两式相加，有

注意到该不等式的形式类似四边形不等式，因为我们用的是反证法，所以我们记$w(j,i)=\sqrt{i-j}$需要证明

也就是

符号方向与上文不同，但是相同的是定理1变号后仍然成立，所以我们要证明

(这里用类似上文的方法可行，不过感觉下面说的方法更有感觉)

记$d=b-a$显然$d>0$，我们要证(这一步是代入$w(j,i)=\sqrt{i-j}$然后换元)

移项得

记$f(x)=\sqrt{x}$，容易发现两边都是拉格朗日中值定理的形式，所以存在$n\in(d,d+1),m\in(d-1,d)$，使得$f’(n)=\frac{\sqrt{d+1}-\sqrt{d}}{1},f’(m)=\frac{\sqrt{d}-\sqrt{d-1}}{1}$，注意到$f’(x)=\frac{1}{2\sqrt{x}}$单调递减且$n<m$所以上式得证。由本题可见，四边形不等式变号后的大部分性质仍然成立，而证明决策单调性也通常从要求证的命题倒推。

引例3

[IOI2000]邮局

题目大意

数轴的正半轴上有$n$个村庄，村庄的横坐标为数轴正半轴上的整点。求在数轴上放$m$个邮局，每个村庄到离自己最近的邮局的距离和的最小值。$m\leq 300,n\leq 2000$

状态转移方程

比较显然，记$F_{i,j}$表示前$i$个村庄放$j$个邮局的最小距离总和，有$F_{i,j}=\min_{0<k<i}{\{F_{k,j-1}+w(k+1,i)\}}$。其中，$w(i,j)$表示在区间$[i,j]$(这里的标号表示村庄按横坐标升序排序后的标号)中放一个邮局的最小距离总和。记$a_i$表示第$i$个村庄的横坐标，将村庄按此升序排序后，记$s_i=\sum_{j=1}^i a_i$，则$w(l,r)=s_r-s_{[\frac{l+r}{2}]}-s_{[\frac{l+r}{2}]-1}+s_{l-1}-[(l+r)\mod 2 = 0]a_{[\frac{l+r}{2}]}$。这里里面带等式的$[]$表示真值符号，其它表示向下取整符号。

这样做时间复杂度是$O(n^2m)$的，需要优化到$O(n^2)$

优化——仍然是决策单调性

既然要找规律，那就在跑一下找规律吧，见下图：

似乎没什么规律

规律当然是有的。我们可以发现，对于同一行的最优决策点，从左至右单调不递减，对于同一列的最优决策点，从上至下单调不递减。实际上我们记$P_{i,j}$为$(i,j)$处的最优决策点，由于我们在同一行中不可能计算出一个位置的相邻两个位置后再计算它本身，则有$P_{i,j-1}\leq P_{i,j}\leq P_{i+1,j}$，读者可以对照上图自行验证。要注意的是，我们为了处理边界问题，就定义$P_{n+1,j}=n$。

那么转移时只要枚举$P_{i,j-1}\leq k \leq P_{i+1,j}$即可，这样的话，复杂度降低为$O(n^2)$，可以通过此题。

正确性？

一般来说，证明这一类二维动态规划的常规方法为先证$w(i,j)$满足四边形不等式，即$w(i,j+1)+w(i+1,j)\geq w(i,j)+w(i+1,j+1)$，然后用归纳法证明$F$满足四边形不等式，最后利用四边形不等式与$P$的最优性得到两个不等式并将之合并得到一个类似$F_{k,j}+w(k+1,i)\leq F_{P_{i,j}}+w(P_{i,j}+1,j)$的式子，也就是所谓$P_{i,j}\geq P_{i,-1}$，同理得到$P_{i+1,j}\geq P_{i,j}$，就证明好了。对于本题的证明，此处略去，请读者自行思考。

补充

别的$BLOG$讲到四边形不等式优化二维动态规划时大多以石子合并的转移方程$F_{i,j}=\min_{i\leq k<j}{\{F_{i,k}+F_{k+1,j}\}}+\sum_{i=l}^{j}a_i$为例，但是合并果子有$O(n\log n)$的做法，没必要使用四边形不等式优化，所以就选了邮局。

引例4

[CmdOI2019]任务分配问题

题目大意

给定一个长度为 $n$ 的排列 $p$，将 $p$ 按照原顺序划分成 $k$ 段，使每一段的顺序对个数和最小。$n\le 25000,k\le 25$

动态转移方程

类似于引例3，可以得到转移方程

其中，$F_{i,j}$ 表示将前 $i$ 个数分为 $j$ 段时每一段顺序对个数和的最小值，$w(i,j)$ 表示区间 $[i,j]$ 内的顺序对个数。这么做是 $O(n^2k)$ 的。

优化

我们发现，$w(i,j)$ 是满足四边形不等式的，所以该转移方程满足决策单调性。但是 $w(i,j)$ 不是很好算，而且 $n$ 是比较大的，这么一来就不能使用引例3的做法。

不过我们发现 $k$ 比较小，而且 $j$ 只会从 $j-1$ 转移而来，所以我们可以考虑做相同的转移 $k$ 次。现在我们将问题转换为了，用上一次的结果 $[0,n-1]$ 去转移这一次的 $[1,n]$。

这边我们要介绍一个全新的东西，它叫做决策单调性分治。由于决策单调性，当前所求的一段连续的区间(就是状态转移方程中 $i$ 那一维的下标)一定是从上一次所求的一段连续的区间转移而来的。我们记 $Solve(l,r,L,R)$ 表示用 $[L,R]$ 这一段上一次所求的连续的区间可以转移至 $[l,r]$ 这一段当前所求的的连续的区间。我们取 $[l,r]$ 的中点 $mid$，然后找到 $mid$ 的最优决策点 $p$(这里当然就算出了动态转移方程中 $mid$ 处的取值)，那么 $[l,mid-1]$ 只可能从 $[L,p]$ 转移而来，$[mid+1,r]$ 只可能从 $[p,R]$ 转移而来，这一步可以由决策单调性得出。于是如此递归分治下去，显然边界就是 $l=r$，不过这里不用特判，因为找 $mid$ 的最优决策点时已经算出动态转移方程 $mid$ 处的取值，而此时 $l=mid$。

注意到算法过程中计算 $w(i,j)$ 都是扩展一格左边界，那么计算 $w(i,j)$ 可以使用类似莫队的思想，用树状数组维护即可。每一层分治的时间复杂度为 $O(n\log n)$，一共分治 $O(\log n)$ 层，这样的分治进行 $k$ 次，故总时间复杂度为 $O(nk\log^2 n)$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// lst[]=>上一次求出的答案，now[]=>当前求的
void Solve(int l,int r,int L,int R){//如上文所述
    int mid=(l+r)>>1,p=mid;
    for(REG int i=L;i<=Min(mid-1,R);++i){
        int ans=w(i+1,mid);
        if(lst[i]+ans<=now[mid]) now[mid]=lst[i]+ans,p=i;
    }
    if(l<mid) Solve(l,mid-1,L,p);
    if(r>mid) Solve(mid+1,r,p,R);
}

int Work(){
    for(REG int i=1;i<=n;++i) lst[i]=now[i]=0x7f7f7f7f;
    for(REG int i=1;i<=k;++i){
        Sovle(1,n,0,n-1);//从[0,n-1]转移至[1,n]
        for(REG int j=1;j<=n;++j) lst[j]=now[j];
    }
    return now[n];
}

总结

引例1主要引入一维动态规划的决策单调性优化。

引例2主要是说明 $\min/\max$ 不影响应用决策单调性优化，只是需要将不等号变方向。

引例3主要引入二维动态规划中 $w(i,j)$ 可以快速且方便计算的决策单调性优化。

引例4主要引入二维动态规划中 $w(i,j)$ 不可以快速且方便计算的决策单调性分治方法。