决策单调性优化讲解

LCuter

2019-10-31 13:19:02

Algo. & Theory

临时给自己新搭的博客做个广告……

https://lcuter.gitee.io

概论

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

引例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 k<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_{taill},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

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是最优的，所以我们有：

F_{P_j}+w(P_j,j)< F_{P_i}+w(P_i,j) F_{P_i}+w(P_i,i)< F_{P_j}+w(P_j,i)

两式相加，有

w(P_i,i)+w(P_j,j)< w(P_i,j)+w(P_j,i)

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

w(P_i,i)+w(P_j,j)\geq w(P_i,j)+w(P_j,i)

也就是

\forall a<b<c<d,w(a,d)+w(b,c)\geq w(a,c)+w(b,d)

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

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

于是定理1就证明完了

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

\forall j<i,w(j+1,i)+w(j,i+1)\ge w(j,i)+w(j+1,i+1)

移项，有

w(j+1,i)-w(j+1,i+1)\ge w(j,i)-w(j,i+1)

记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，则有

a_{P_j}+\sqrt{j-P_j}>a_{P_i}+\sqrt{j-P_i} a_{P_i}+\sqrt{j-P_j}>a_{P_j}+\sqrt{i-P_j}

两式相加，有

\sqrt{i-P_i}+\sqrt{j-P_j}>\sqrt{j-P_i}+\sqrt{i-P_j}

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

w(P_i,i)+w(P_j,j)\leq w(P_i,j)+w(P_j,i)

也就是

\forall a<b<c<d,w(a,d)+w(b,c)\leq w(a,c)+w(b,d)

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

\forall a<b,w(a,b+1)+w(a+1,b)\leq w(a,b)+w(a+1,b+1)

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

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

\sqrt{d-1}+\sqrt{d+1}\leq\sqrt{d}+\sqrt{d}

移项得

\frac{\sqrt{d+1}-\sqrt{d}}{1}\leq \frac{\sqrt{d}-\sqrt{d-1}}{1}

记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所以上式得证。

另外，还可以逆向分母有理化，得到 \dfrac{1}{\sqrt{d+1}+\sqrt{d}} ，这个显然是单调递减的。

由本题可见，四边形不等式变号后的大部分性质仍然成立，而证明决策单调性也通常从要求证的命题倒推。

引例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}=\min_{0\le k<i}\{F_{k,j-1}+w(k+1,i)\}

其中，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

// 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) 不可以快速且方便计算的决策单调性分治方法。