Chlience

【算法】NOIP前的一些板子 第二弹
动态规划几种经典转移方程$1D / 1D : f[i] = min(f[j] , cost(j + 1 , i))...
扫描右侧二维码阅读全文
31
2018/10

【算法】NOIP前的一些板子 第二弹

动态规划

几种经典转移方程

$1D / 1D : f[i] = min(f[j] , cost(j + 1 , i))$

$2D / 0D: f[i][j] = min(f[i - 1][j] + x_i , f[i][j - 1] + y_i , f[i - 1][j - 1] + z_i)$

$2D / 1D : f[i][j] = cost(i , j) + min(f[i][k] + f[k + 1][j])$

$f[i][j] = min(f[i - 1][k] + cost(i , j , k))$

$2D / 2D : f[i][j] = min(f[i'][j'] + w(i' , i , j' , j))$

线性DP

这里的线性指的是状态的排布成线性

一个比较多/杂的分类,当然也是最常见的

一般来说方程为 $1D / 1D : f[i] = min(f[j] , cost(j + 1 , i))$

当然复杂一点的也有很多,主要考优化比较多吧

区间DP

通常每个区间答案和子区间贡献贡献相关

方程多为 $2D / 1D : f[i][j] = cost(i , j) + min(f[i][k] + f[k + 1][j])$

树形DP

一类比较看出来的DP吧

首先要是一棵树,然后要能够动归(逃

通常每个节点的转移仅仅和父亲/儿子相关

由于其从父亲节点获取转移需要先处理完父亲的信息,所以一般DP两遍,也就是常常所说的换根DP

但是有些神奇的题目是需要将所有儿子(子树)中并起来算贡献,比如说 Wannafly 27 蓝魔法师 ,这个东西看起来比较复杂,其实直接暴力合并子树答案就行,可以使用 $FFT$ 优化一类的东西(boshi 哭晕在厕所)、

状压DP

近年来很经典的状压就是 NOIP 2017 宝藏

复杂度一般带 $2^n$ 枚举子集为 $3^n​$

$$f[s| t]=\min (f[s]+cost(s , t))$$

所以一般都是一眼出

至于怎么打,呵呵

数位DP

通常是对于按位进行DP

当然如果你要是每一位的状态都设计成 $[0,9]$ ,那么这和枚举也没什么区别

一般来说我们控制上界枚举时,能够很简单的计算大部分时刻的贡献,对于特殊点特殊计算即可

有时候需要判断前导零和是否达到上界,可以用搜索实现(按位循环其实也好啦!)

概率期望DP

一类比较复杂的DP,基本上放上来不是神就是坑,当然大部分时候是神坑

对于期望 DP,我们一般采用 逆序 的方式来定义状态,即考虑从当前状态到达终点的期望代价

因为在大多数情况下,正向计算并不能很好的计算出期望,不信你可以试试(逃

推荐一个博客 概率与期望总结

DP 优化

单调栈/单调队列优化

看题目情况,基本一眼出

斜率优化

考虑两个状态之间对于当前转移的优劣,若有单调性,直接将劣的删去;若没有单调性,每次在队列中二分查找

矩阵乘法优化

这个一般比较显然,转移位置不会太多

凸优化(带权二分)

带权二分一般是解决有次数限制的问题,并且要求的最大/最小值和次数单调相关,那么可以通过带权来限制次数,从而优化DP

数据结构优化

这个一般就是线段树 $or$ 树状数组优化区间最值啦,或者区间更新也是有可能的

Last modification:October 31st, 2018 at 07:31 pm

Leave a Comment