「OI之路」05动态规划-2-动态规划进阶

动态规划进阶

1D/1D动态规划

状态和转移都是一维的动态规划

$f(i)=f(j)+w(j,i)$

单调队列

能转移的集合有单调性

主要步骤:

  1. 移除无效元素
  2. 计算队首的最优g,得到f(i)的最优结果
  3. 计算新的g,放入队列中,并维护单调性

斜率优化

对于权值的要求:$w(j,i)=a_i+b_j+c_i \times d_j$

如果j在i之前已经计算出来了,化一下式子:$f(i)=(d_j) \cdot (c_i) +b_j+f(j)+a_i$
不难看出这是一个一次函数,ci是带入的未知元,这个可以用李超树轻松解决,复杂度下限是nlogn
而运用斜率优化,有些题还是要nlogn,但有些题可以达到线性(文末有讨论)

换一种思路,考虑将j本身的东西作为x和y,也就是变成点
那么对于i,它的决策也可以是这种形式:$f(j)+b_j=(-c_i) \cdot (d_j) +f(i)-a_i$
截距:直线与y轴的交点的纵坐标
那么我们的目的就是最小化截距
就是一个直线,其斜率和i有关,从下往上移直到碰到第一个点,就是最优决策点
显然只有凸壳上的点是有用的

然后下面的内容就要结合题目的具体性质了
A. 点的x坐标是单调的

  1. 提供的直线的斜率是单调递增的
    这种情况的话,显然这个凸壳内部相邻点的斜率是单调递增的,否则不会有贡献
    而且决策点具有单调性,左边的部分无需保留,通常用单调队列实现
  2. 提供的直线的斜率是不单调的
    此时决策点不单调,不过因为维护好了凸壳,可以在上面二分(某个左右都更差的位置)

B. 点的x坐标是不单调的
平衡树动态插入来维护或者用cdq分治处理

练习

入门经典题是玩具装箱,当时写的题解是从数学的角度,现在用几何角度基本是秒杀的

另外如「JSOI2011」柠檬

决策单调性

年轻时一直不喜欢这东西,觉得就是打表,证明冗长,题目少
现在真正研究下,才发现这东西不简单,也不是题目少,只是境界不够,所以看不懂或没耐心的也没关系,回去修炼一年再来吧
不过冗长的数学证明这事情,至今水平也不太足,但如果真的太长的墙裂建议别看,没多久就会忘记的


如果w满足下面的四边形不等式,就可知满足决策单调性,决策点是单调递增的(注意我用的是):

$\forall a<b < c<d, w(a,c)+w(b,d) 不劣于 w(a,d)+w(b,c)$

年轻的我曾经给出了当时觉得已经算简洁的数学证明:
$$
想证明 \forall j<i,fm_j \le fm_i,假定问题要最小化,最大化没区别\\对于x \le fm_j,T=dp(x)+w(x,i)-dp(fm_j)-w(fm_j,i)\\根据上面的式子,x \le fm_j \le j \le i,w(x,j)+w(fm_j,i) \le w(x,i)+w(fm_j,j)\\T \ge dp(x)-dp(j)+w(x,j) \ge 0,因此x没有fm_j优,因此fm_i \ge fm_j
$$
年迈的我选择跳过这段证明而采用更直观的方法:所谓不满足决策单调性就是$fm_i<fm_j \le j \le i$,此时两人花在转移上的花费之和相当于不等式的后者,换成前者一定会导致$dp_i+dp_j$变优,因此一定有一个变优,但我们的dp定义就是不能再变优的了

这个证明思路其实会始终贯穿,即使在二维、环等各种变形中,精髓还是不变的:形似最短路的dp这类东西本身定义的时候是所有状态都最优了,然后四边形不等式给出了一种交换使得两个状态和变优这样一个不应出现的情况

有些题显然满足(如CF321E画个图就行),不显然就拍上,假了再说


类型一:$dis_{i<j}=w(i,j)$,w满足四边形不等式,求0到n最短路

例题NOI2009诗人小Gbzoj2216 「Poi2011」Lightning Conductor

必须从左往右计算出dp值,考虑每个点会作为哪些地方的决策点

从前往后加入考虑的话显然是一段后缀,二分出位置,单调队列维护每个点当前最优决策点即可,$O(nlog)$

类型二:$dis_{i<j}=w(i,j)$,w满足四边形不等式,求最短的点数为k路径

例题CF321E Ciel and Gondolas(bzoj5311 贞鱼)「IOI2000」Post Officebzoj5125[Lydsy1712月赛]小Q的书架CF868F Yet Another Minimization Problem、「IOI2014」holiday(写了题解)

做k轮dp,但每轮内部先计算哪个没有要求,此时推荐写分治,不容易写错,$O(knlog)$

每次在可用决策点区间内暴力枚举求出mid的决策点,那么每层分治决策点区间长度和是$O(n)$级别的,所以每轮是nlogn的

另外,如果一次只询问一个k,借助带权二分可以达到更优秀的$O(nlog^2)$,详见专题

类型三:环上求权值最小的点数为k集合,边权为相邻点间w和,w从相对位置角度满足四边形不等式

例题:Yuhao Du Contest 5 I,并没有地方交,所以下面是口胡

做法1:因为分治做法$O(nklog)$中包含k,可以用套路集锦-数学-5中的方法,$O(5n^2log)$

做法2:先随便用某个做法初始化出一组解,那么每个相邻两点构成的一开一闭区间中,其他解一定都是每个区间恰一个点。固定第一组中起点的话就是要求出到最后一组每个点的最短距离然后枚举每个来统计答案(看做竖着的k个区间可能会比较直观)。将最短那个区间(不超过n/k)看做第一组,枚举每个起点,一层一层跑任意算法(推荐分治),确定性算法,$O(n/k*nlogn)$

标算:用带权二分初始化出一组解,四边形不等式的限制竖着看就是两条转移直线不能交叉,因此一个起点的路径会把每一组分为左右两半(重叠1),因此可以套一个分治,每次求出第一组区间中mid为起点,花费$(\sum_i 第i组大小)log$的时间求出这个起点的最优方案并把每组分为两半。虽然每次分离时,k组中每个左右区间都会有1的重叠,记$ln=第一组大小$,那么重叠部分带来的影响为$\sum_{i=0}^{log_2 ln} 2^i*k=O(k*ln)$,因此我们依然选最小那个作为第一组,总复杂度为$O(nlog^2)$

非常规类型

「IOI2013」wombats

Circular edit distance


CF321E:k轮w满足四边形不等式的1d1d动归,下文轮数(最短路长度)放在状态的第二维

合并石子:$f(l,r)=min\ f(l,k)+f(k+1,r)+w(l,r)$中w满足四边形不等式

「IOI2013」 wombats:与1d1d、四边形不等式无关,但也满足决策单调性

他们看起来除了状态都是二维外没啥关系,然而笔者认为他们代表了二维决策单调性的几种参考方向

核心就是决策点满足不等式:$opt(i,k)=(i,k)的决策点,opt(i,k-1) \le opt(i,k) \le opt(i+1,k)$,稍后证明

只要有了这个不等式,可以写出fo(j,1,k) fd(i,n,1) fo(fm,opt(i,j-1),opt(i+1,j)) f(fm,j-1)->f(i,j)(可见非常好写)。

复杂度的话,考虑每种$ln=i-j$对应所有状态,他们的决策点连起来,精准覆盖了1到n,因此就是$O(n^2)$

IOI那题具体见题解(口胡,不过应该没错),合并石子能数学证明但可以感受也不展开了,说说1d1d

对于长度分别为k-1和k的两条路径,起点终点相同,因为不能出现四边形不等式的情况,k-1路径每一步一定恰好跨过一个k路径中的点(包括刚好在上面,此时前面部分都是重叠的)。因此去掉两条路径前面公共的部分,一定是交错出现的,感觉这个性质还有挖掘空间

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/4bab.html
转载请注明出处,谢谢!