【OI之路】05动态规划-2-1d1d动态规划

1D/1D动态规划
状态为n,转移为n的dp方程
动态规划的优化-周尚彦.pdf

单调队列

主要步骤:

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

有一道比较变态的变形题:
Cut the Sequence

斜率优化

这个东西学了n次,前面n-1次都没学扎实(教练水平有限)
随着实力的提升,这次细细研究周尚彦的论文,终于彻底搞明白了
所以我也尽力讲清楚,但开始研究之前请确保有扎实的基础(如提高一等水平)

斜率优化主要可以从数学和图形的角度去理解,
数学方面的话可以看我玩具装箱的题解,本文以图形为主(更有助于后期的提升)

dp方程的基本形式(不能有二维数组):
$f(i)=f(j)+w(j,i),w(j,i)=a_i+b_j+c_i \times d_j$
如果j在i之前已经计算出来了,显然可以化一下柿子
$f(i)=(d_j) \cdot (c_i) +a_i+b_j+f(j)$
不难看出这是一个一次函数,i是带入的未知元,这个可以用李超树轻松解决
看到别人说要化成一次函数的形式,这是我最先想到的做法,然而这样的复杂度下限是nlogn的
然而有些题,使用斜率优化可以线性解决

换一种思路,考虑将j本身的东西所谓x和y,也就是变成点
那么对于i,它的决策也可以是这种形式:
$f(j)+b_j=(-c_i) \cdot (d_j) +f(i)-a_i$
截距:直线与y轴的交点的纵坐标
那么我们的目的就是最小化截距

据说这是一个线性规划问题,但我不清楚这是什么……但这和我们要讲的无关
总之就是一个直线,其斜率和i有关,从下往上移直到碰到第一个点,就是最优决策点
显然只有某个凸壳上的点是有用的(min则下凸壳)


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

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

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

练习

详细地讲讲这个入门好题(仅从数学的角度):
玩具装箱
好文章推荐:
MashiroSky

四边形不等式

如果转移满足该不等式,则称满足决策单调性
形式1:对于 $a \leq b \leq c \leq d,w(a,d)+w(b,c) \geq w(a,c)+w(b,d)$
(简单记为:交叉小于包含)
形式2: $w(a,b+1)+w(a+1,b) \geq w(a,b)+w(a+1,b+1)$
考场上可以考虑暴力打出决策点的表,验证单调性

一维:
$f(i)=min f(j)+w(j,i)$
一维状态例题:诗人小G
这个套路还是很好用的

然后还有一种写法,某些情况下可能更好写
就是分治,每次暴力处理mid的决策点

二维(虽然这个不属于1d1d,但是也顺便讲讲):
$f(l,r)=min f(l,k)+f(k+1,r)+w(l,r)$
如果w满足四边形不等式,则f也满足四边形不等式
如果f满足四边形不等式,则 $fm(l,r-1) \leq fm(l,r) \leq fm(l+1,r)$
即f的决策,在同一行、同一列上单调递增

例题:合并石子
显然其w满足四边形不等式(取等),则f也满足,那么决策的区间是确定了的
然后你考虑每种ln
$l=1,fm(1,ln-1) -> fm(2,ln)$
$l=2,fm(2,ln) -> fm(3,ln+1)$
……
也就是枚举范围连起来只有一个n
(感觉这种东西谁会想到啊……)
l
推荐文章:
https://www.cnblogs.com/mlystdcall/p/6525962.html
https://blog.csdn.net/noiau/article/details/72514812

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