专栏文章

决策单调性优化讲解

LLCuter
算法·理论参与者 30已保存评论 32

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
32 条
当前快照
1 份
快照标识符
@mhz5sfr4
此快照首次捕获于
2025/11/15 01:55
4 个月前
此快照最后确认于
2025/11/29 05:24
3 个月前
查看原文
临时给自己新搭的博客做个广告……
https://lcuter.gitee.io

概论

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

引例1

P1912 [NOI2009]诗人小G

题目大意

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

状态转移方程

重点在于优化动态规划，所以我直接放动态转移方程了
记aia_i为第ii句诗的长度，sis_i为前ii句诗的总长度加上ii个空格的长度，即si=i+∑j=1iais_i=i+\sum_{j=1}^{i}a_i，LL为标准长度。记FiF_i表示摆放前ii句诗的最小不协调度，则有Fi=min⁡0≤k<i{Fk+∣si−sk−L−1∣P}F_i=\min_{0\leq k<i}{\{F_k+|s_i-s_k-L-1|^P\}}。这个状态转移方程的意思是前kk句诗按它的最优方案排列，第k+1k+1句诗到第ii句诗另起一行。
显然这个状态转移的时间复杂度是O(n2)O(n^2)的，无法通过本题的数据范围，所以我们考虑优化。

优化——决策单调性

动态规划的优化基本上都是排除冗余的计算，要想优化这个动态规划，我们需要找到合适的性质，并合理利用该性质排除冗余的计算。既然要找性质，那就来打个表找找规律吧,我手造了一组数据并跑了一下，得到如下结果：
观察到，最优值基本上没什么规律，但是最优决策点竟然是单调不递减的！但是，最优决策点单调不递减有什么用呢？
我们记PiP_i为第ii个位置的最优决策点，显然PP单调不下降。在我们求出某一个FiF_i的时候，我们要求出仅考虑以1−i1-i为决策点的时候，哪一段的最优决策点是ii。由于决策单调性，我们可以在PP中找到一个点jj，对于任意k<jk<j有Pk<iP_k<i，对于任意k≥jk\geq j有Pk≥iP_k\geq i。事实上，因为我们仅考虑以1−i1-i为决策点，所以我们在计算到ii时可以认为上面的表述可以转换为"对于任意k<jk<j有Pk<iP_k<i，对于任意k≥jk\geq j有Pk=iP_k= i"，我们可以这么做的原因是在之后的计算中不以ii为最优决策点的i′i'会被其它的决策点覆盖。关于上面的例子，我绘制了一份PP的图片，如下图：
所以我们现在的问题转换为：维护一个数组PP，找到一个点使得这个点之前的ii都会被其它决策吊打，但在这个点及这个点之后，ii可以吊打之前的所有决策，并将这个点即后面的所有点的值赋值为ii
我们先考虑如何找到该点：枚举的复杂度是O(n)O(n)，但是由于单调性，我们是可以利用二分将复杂度降低至O(log⁡n)O(\log n)的。
接着考虑后一个操作，注意到这是一个区间赋值问题，故我们可以借用类似于珂朵莉树的思想：维护一个队列，队列中的元素为一个三元组(l,r,x)(l,r,x)表示区间[l,r][l,r]的值为xx。于是，在我们计算完FiF_i时，我们从队尾开始检查，如果队尾的三元组(ltail,rtail,xtail)(l_{tail},r_{tail},x_{tail})的ltaill_{tail}取xtailx_{tail}不如ii，那么弹出该三元组，如果rtailr_{tail}取xtailx_{tail}比ii好，但是ltaill_{tail}取xtailx_{tail}比ii好，此时我们在区间[ltaill,rtail][l_{taill},r_{tail}]内二分，找出满足要求的点midmid，将队尾三元组改为(ltail,mid−1,xtail)(l_{tail},mid-1,x_{tail})，并插入(mid,n,i)(mid,n,i)即可。
那么在开始计算FiF_i时如何找到PiP_i呢？只要我们在开始计算前在队头弹出过时的三元组，即队头的三元组(lhead,rhead,xhead)(l_{head},r_{head},x_{head})的rhead=i−1r_{head}=i-1时，我们弹出队头，否则令lhead=il_{head}=i。那么此时队头就是PiP_i的值了，这个操作是不是让你想起了单调队列？事实上在单调队列优化动态规划中，单调队列维护的是FiF_i，而在这里单调队列维护的是PiP_i，这便是决策单调性的性质带来的好处。另外，在实现中我们没必要真的维护三元组，只需记录每一段区间的最后一个位置与区间的值即可。
什么？你问我复杂度？注意到队列中每一个元素至多被入队出队一次，二分只会做nn次，所以复杂度应该是O(nlog⁡n)O(n\log n)的我口胡的。那么本题就完美解决啦不，你会因为字符串等问题调很久的，我说的

Code

CPP
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的内容后，我发现可以有更能让人听懂的证明
我们可以用反证法，假设∃j<i,Pj>Pi\exists j<i,P_j>P_i，有Pi<Pj<j<iP_i<P_j<j<i
记w(j,i)=∣si−sj−L−1∣Pw(j,i)=|s_i-s_j-L-1|^P，因为PP是最优的，所以我们有：
FPj+w(Pj,j)<FPi+w(Pi,j)F_{P_j}+w(P_j,j)< F_{P_i}+w(P_i,j)
FPi+w(Pi,i)<FPj+w(Pj,i)F_{P_i}+w(P_i,i)< F_{P_j}+w(P_j,i)
两式相加，有
w(Pi,i)+w(Pj,j)<w(Pi,j)+w(Pj,i)w(P_i,i)+w(P_j,j)< w(P_i,j)+w(P_j,i)
因为我们是用反证法，所以只要证明
w(Pi,i)+w(Pj,j)≥w(Pi,j)+w(Pj,i)w(P_i,i)+w(P_j,j)\geq w(P_i,j)+w(P_j,i)
也就是
∀a<b<c<d,w(a,d)+w(b,c)≥w(a,c)+w(b,d)\forall a<b<c<d,w(a,d)+w(b,c)\geq w(a,c)+w(b,d)
我们称该不等式为四边形不等式，特别地，若原状态转移方程是取max⁡\max，则要将≥\geq改为≤\leq。要想证明这个不等式，先得证明一个定理，这个定理将大大减少证明的难度
  • 定理1 若一个定义在整数集上的二元函数w(x,y)w(x,y)满足对于任意定义域内的a<ba<b，都有w(a,b+1)+w(a+1,b)≥w(a,b)+w(a+1,b+1)w(a,b+1)+w(a+1,b)\geq w(a,b)+w(a+1,b+1)成立，则w(x,y)w(x,y)满足四边形不等式
要想证明定理1，先证明两个引理
  • 引理1 若一个定义在整数集上的二元函数w(x,y)w(x,y)满足对于任意定义域内的a<ba<b，都有w(a,b+1)+w(a+1,b)≥w(a,b)+w(a+1,b+1)w(a,b+1)+w(a+1,b)\geq w(a,b)+w(a+1,b+1)成立，则对任意定义域内的a<b<ca< b< c有w(a,c+1)+w(b,c)≥w(a,c)+w(b,c+1)w(a,c+1)+w(b,c)\geq w(a,c)+w(b,c+1)
  • 证明
    • 考虑数学归纳法，若kk为一非负整数，记b=a+kb=a+k，且b=a+k<cb=a+k<c
    • 当k=1k=1
    • 显然由a<ca<c可得
    • w(a,c+1)+w(a+1,c)≥w(a,c)+w(a+1,c+1)w(a,c+1)+w(a+1,c)\ge w(a,c)+w(a+1,c+1)
    • 即
    • w(a,c+1)+w(b,c)≥w(a,c)+w(b,c+1)w(a,c+1)+w(b,c)\ge w(a,c)+w(b,c+1)
    • 当k>1k>1
    • 若有
    • w(a,c+1)+w(a+k−1,c)≥w(a,c)+w(a+k−1,c+1)w(a,c+1)+w(a+k-1,c)\geq w(a,c)+w(a+k-1,c+1)
    • 因为a+k<ca+k<c
    • w(a+k−1,c+1)+w(a+k,c)≥w(a+k−1,c)+w(a+k,c+1)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)≥w(a,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)≥w(a,c)+w(b,c+1)w(a,c+1)+w(b,c)\ge w(a,c)+w(b,c+1)
    • 证毕
  • 引理2 若一个定义在整数集上的二元函数w(x,y)w(x,y)满足对于任意定义域内的a<b<ca< b< c有w(a,c+1)+w(b,c)≥w(a,c)+w(b,c+1)w(a,c+1)+w(b,c)\geq w(a,c)+w(b,c+1)，则w(x,y)w(x,y)满足四边形不等式
  • 证明
    • 若kk是一个非负整数,记d=c+kd=c+k
    • 当k=1k=1
    • 显然由b<cb<c有
    • w(a,c+1)+w(b,c)≥w(a,c)+w(b,d)w(a,c+1)+w(b,c)\ge w(a,c)+w(b,d)
    • 即
    • w(a,d)+w(b,c)≥w(a,c)+w(b,d)w(a,d)+w(b,c)\ge w(a,c)+w(b,d)
    • 当k>1k>1
    • 假设有
    • w(a,c+k−1)+w(b,c)≥w(a,c)+w(b,c+k−1)w(a,c+k-1)+w(b,c)\ge w(a,c)+w(b,c+k-1)
    • 因为c+k>bc+k>b
    • w(a,c+k)+w(b,c+k−1)≥w(a,c+k−1)+w(b,c+k)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)≥w(a,c)+w(b,c+k)w(a,c+k)+w(b,c)\ge w(a,c)+w(b,c+k)
    • 即∀a<b<c<d,w(a,d)+w(b,c)≥w(a,c)+w(b,d)\forall a<b<c<d,w(a,d)+w(b,c)\ge w(a,c)+w(b,d)
于是定理1就证明完了
那么，现在只需要证明w(j,i)=∣si−sj−L−1∣Pw(j,i)=|s_i-s_j-L-1|^P满足
∀j<i,w(j+1,i)+w(j,i+1)≥w(j,i)+w(j+1,i+1)\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)≥w(j,i)−w(j,i+1)w(j+1,i)-w(j+1,i+1)\ge w(j,i)-w(j,i+1)
记u=si−sj−L−1,v=si−sj+1−L−1u=s_i-s_j-L-1,v=s_i-s_{j+1}-L-1
只需证∣v∣P−∣v+ai+1+1∣P≥∣u∣P−∣u+ai+1+1∣P|v|^P-|v+a_{i+1}+1|^P\ge |u|^P-|u+a_{i+1}+1|^P
因为u>vu>v，所以只需证明函数f(x)=∣x∣P−∣x+c∣Pf(x)=|x|^P-|x+c|^P(cc为常数)单调不递增即可
可以分类讨论并利用导数解决，此处不赘述

引例2

[POI2011]Lightning Conductor

题目大意

给定一个正整数nn与非负整数数列ana_n，对于每一个i∈[1,n]i\in [1,n]，求一个最小的非负整数pp使得∀j∈[1,n],aj≤ai+p−∣i−j∣\forall j\in [1,n],a_j\leq a_i+p-\sqrt{|i-j|}，n≤5×105n\leq 5\times 10^5

伪状态转移方程(大雾

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

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

手玩一下样例，容易发现这个仍然满足决策单调性。那么我们可以按照上面的方法计算它。但是正确性呢？我们考虑反证法。仍然用PP表示最优决策
假设∃i,j∈[1,n],i<j,Pj>Pi\exists i,j\in [1,n],i<j,P_j>P_i，则有
aPj+j−Pj>aPi+j−Pia_{P_j}+\sqrt{j-P_j}>a_{P_i}+\sqrt{j-P_i}
aPi+j−Pj>aPj+i−Pja_{P_i}+\sqrt{j-P_j}>a_{P_j}+\sqrt{i-P_j}
两式相加，有
i−Pi+j−Pj>j−Pi+i−Pj\sqrt{i-P_i}+\sqrt{j-P_j}>\sqrt{j-P_i}+\sqrt{i-P_j}
注意到该不等式的形式类似四边形不等式，因为我们用的是反证法，所以我们记w(j,i)=i−jw(j,i)=\sqrt{i-j}需要证明
w(Pi,i)+w(Pj,j)≤w(Pi,j)+w(Pj,i)w(P_i,i)+w(P_j,j)\leq w(P_i,j)+w(P_j,i)
也就是
∀a<b<c<d,w(a,d)+w(b,c)≤w(a,c)+w(b,d)\forall a<b<c<d,w(a,d)+w(b,c)\leq w(a,c)+w(b,d)
符号方向与上文不同，但是相同的是定理1变号后仍然成立，所以我们要证明
∀a<b,w(a,b+1)+w(a+1,b)≤w(a,b)+w(a+1,b+1)\forall a<b,w(a,b+1)+w(a+1,b)\leq w(a,b)+w(a+1,b+1)
(这里用类似上文的方法可行，不过感觉下面说的方法更有感觉)
记d=b−ad=b-a显然d>0d>0，我们要证(这一步是代入w(j,i)=i−jw(j,i)=\sqrt{i-j}然后换元)
d−1+d+1≤d+d\sqrt{d-1}+\sqrt{d+1}\leq\sqrt{d}+\sqrt{d}
移项得
d+1−d1≤d−d−11\frac{\sqrt{d+1}-\sqrt{d}}{1}\leq \frac{\sqrt{d}-\sqrt{d-1}}{1}
记f(x)=xf(x)=\sqrt{x}，容易发现两边都是拉格朗日中值定理的形式，所以存在n∈(d,d+1),m∈(d−1,d)n\in(d,d+1),m\in(d-1,d)，使得f′(n)=d+1−d1,f′(m)=d−d−11f'(n)=\frac{\sqrt{d+1}-\sqrt{d}}{1},f'(m)=\frac{\sqrt{d}-\sqrt{d-1}}{1}，注意到f′(x)=12xf'(x)=\frac{1}{2\sqrt{x}}单调递减且n<mn<m所以上式得证。
另外，还可以逆向分母有理化，得到 1d+1+d\dfrac{1}{\sqrt{d+1}+\sqrt{d}} ，这个显然是单调递减的。
由本题可见，四边形不等式变号后的大部分性质仍然成立，而证明决策单调性也通常从要求证的命题倒推。

引例3

[IOI2000]邮局

题目大意

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

状态转移方程

比较显然，记Fi,jF_{i,j}表示前ii个村庄放jj个邮局的最小距离总和，有Fi,j=min⁡0<k<i{Fk,j−1+w(k+1,i)}F_{i,j}=\min_{0<k<i}{\{F_{k,j-1}+w(k+1,i)\}}。其中，w(i,j)w(i,j)表示在区间[i,j][i,j](这里的标号表示村庄按横坐标升序排序后的标号)中放一个邮局的最小距离总和。记aia_i表示第ii个村庄的横坐标，将村庄按此升序排序后，记si=∑j=1iais_i=\sum_{j=1}^i a_i，则w(l,r)=sr−s[l+r2]−s[l+r2]−1+sl−1−[(l+r)mod  2=0]a[l+r2]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(n2m)O(n^2m)的，需要优化到O(n2)O(n^2)

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

既然要找规律，那就在跑一下找规律吧，见下图：
似乎没什么规律
规律当然是有的。我们可以发现，对于同一行的最优决策点，从左至右单调不递减，对于同一列的最优决策点，从上至下单调不递减。实际上我们记Pi,jP_{i,j}为(i,j)(i,j)处的最优决策点，由于我们在同一行中不可能计算出一个位置的相邻两个位置后再计算它本身，则有Pi,j−1≤Pi,j≤Pi+1,jP_{i,j-1}\leq P_{i,j}\leq P_{i+1,j}，读者可以对照上图自行验证。要注意的是，我们为了处理边界问题，就定义Pn+1,j=nP_{n+1,j}=n。
那么转移时只要枚举Pi,j−1≤k≤Pi+1,jP_{i,j-1}\leq k \leq P_{i+1,j}即可，这样的话，复杂度降低为O(n2)O(n^2)，可以通过此题。

正确性？

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

补充

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

引例4

[CmdOI2019]任务分配问题

题目大意

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

动态转移方程

类似于引例3，可以得到转移方程
Fi,j=min⁡0≤k<i{Fk,j−1+w(k+1,i)}F_{i,j}=\min_{0\le k<i}\{F_{k,j-1}+w(k+1,i)\}
其中，Fi,jF_{i,j} 表示将前 ii 个数分为 jj 段时每一段顺序对个数和的最小值，w(i,j)w(i,j) 表示区间 [i,j][i,j] 内的顺序对个数。这么做是 O(n2k)O(n^2k) 的。

优化

我们发现，w(i,j)w(i,j) 是满足四边形不等式的，所以该转移方程满足决策单调性。但是 w(i,j)w(i,j) 不是很好算，而且 nn 是比较大的，这么一来就不能使用引例3的做法。
不过我们发现 kk 比较小，而且 jj 只会从 j−1j-1 转移而来，所以我们可以考虑做相同的转移 kk 次。现在我们将问题转换为了，用上一次的结果 [0,n−1][0,n-1] 去转移这一次的 [1,n][1,n]。
这边我们要介绍一个全新的东西，它叫做决策单调性分治。由于决策单调性，当前所求的一段连续的区间(就是状态转移方程中 ii 那一维的下标)一定是从上一次所求的一段连续的区间转移而来的。我们记 Solve(l,r,L,R)Solve(l,r,L,R) 表示用 [L,R][L,R] 这一段上一次所求的连续的区间可以转移至 [l,r][l,r] 这一段当前所求的的连续的区间。我们取 [l,r][l,r] 的中点 midmid，然后找到 midmid 的最优决策点 pp(这里当然就算出了动态转移方程中 midmid 处的取值)，那么 [l,mid−1][l,mid-1] 只可能从 [L,p][L,p] 转移而来，[mid+1,r][mid+1,r] 只可能从 [p,R][p,R] 转移而来，这一步可以由决策单调性得出。于是如此递归分治下去，显然边界就是 l=rl=r，不过这里不用特判，因为找 midmid 的最优决策点时已经算出动态转移方程 midmid 处的取值，而此时 l=midl=mid。
注意到算法过程中计算 w(i,j)w(i,j) 都是扩展一格左边界，那么计算 w(i,j)w(i,j) 可以使用类似莫队的思想，用树状数组维护即可。每一层分治的时间复杂度为 O(nlog⁡n)O(n\log n)，一共分治 O(log⁡n)O(\log n) 层，这样的分治进行 kk 次，故总时间复杂度为 O(nklog⁡2n)O(nk\log^2 n)。

Code

CPP
// 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⁡\min/\max 不影响应用决策单调性优化，只是需要将不等号变方向。
引例3主要引入二维动态规划中 w(i,j)w(i,j) 可以快速且方便计算的决策单调性优化。
引例4主要引入二维动态规划中 w(i,j)w(i,j) 不可以快速且方便计算的决策单调性分治方法。

评论

共 32 条评论，欢迎与作者交流。

正在加载评论...