首页 > 代码库 > Evensgn的OI学习笔记（一）——动态规划及其优化
Evensgn的OI学习笔记（一）——动态规划及其优化
Author : Evensgn
Date : 2014-12-08
蒟蒻也要写笔记啦~
（1）矩阵乘法优化DP
矩阵乘法：
一个 a*b 的矩阵 M1 与一个 b*c 的矩阵 M2 相乘，得到一个 a*c 的矩阵 M3。
M3[i][j] = sigma(M1[i][k] * M2[k][j]) ( i <= a; j <= c; k <= b )
M3 的一个元素 M3[i][j] 是矩阵 M1 的第 i 行与 M2 的第 j 列的每一个对应元素乘积的和。
注意：矩阵 M1 的列数与矩阵 M2 的行数必须相同，否则无法相乘。（因此，只有行数与列数相等的矩阵才能有乘方。）
运算规律：矩阵乘法满足结合律，但不满足交换律。（交换后甚至有可能无法相乘。）
矩阵乘法优化线性递推式：
f[n] = f[n-1] * A + f[n-2] * B , 要求快速求出 f[n]
我们可以构造一个 1*2 的初始矩阵，开始时为 [ f[1] f[2] ] , 我们需要得到的下一个矩阵是 [ f[2] f[3] ] ,即为 [ f[2] (f[2] * A + f[1] * B) ]。
那么，我们应该构造一个 2*2 的“转移矩阵”，第一行 [ 0 B ] ， 第二行 [ 1 A ] , 将初始矩阵与转移矩阵相乘就能得到 [ f[2] f[3] ] 。
将矩阵 [ f[2] f[3] ] 再与转移矩阵相乘，就能得到 [ f[3] f[4] ]。那么我们要快速的求出 f[n] ，就可以使用矩阵乘法的结合律。
为了求出 f[n] , 我们要求出 [初始矩阵] * ([转移矩阵]^(n-1)) 。那么我们可以先把后面转移矩阵的乘幂求出，再用初始矩阵与它相乘。
矩阵的乘幂同样可以使用快速幂在 O(logn) 的时间复杂度内求出。
矩阵乘法优化DP：
某一类DP的状态转移方程，也是一个线性递推式，f[i][] 只与 f[i-1][] 有关，比如下面这道例题：
有一个n个点m有向边的图，问：从1出发，经过L条边后恰好到达n有多少条路径？答案模p。 每条边可以被重复经过多次，并且被重复计数。N<=100；L<=10^15 。
我们使用状态 f[i][j] ， 表示经过 i 条边到达 j 的路径条数，那么状态转移方程即为：
f[i][j] = sigma(Map[k][j] * f[i-1][k]) 其中 Map[k][j] 为从 k 到 j 的边数。
这个状态转移方程完全符合使用矩阵乘法优化的条件，因为 f[i][] 只与 f[i-1][] 有关，并且所有的 Map[k][j] 都是已知且固定不变的。
我们就使用一个f[0][] 数组作为初始矩阵，只有 f[0][1] 为 1， 所以初始矩阵为 [ 1 0 0 0 0 ..... 0 ] ，而转移矩阵就是 Map[][] 。这样就可以快速求出
f[L][] ，也就是要求的答案 f[L][n] 。
另一个更复杂一些的例题：BZOJ-1297 迷路：
每条边有一个边权w[i](1<=w[i]<=5)，问：经过长度为L的路径后恰好到达n的路径数模p。 N<=20,m<=1000，L<=10^15 。
那么，首先来看数据范围，w[i] <= 5 , sth神犇教育我们 ： 看到小与等于10的数据范围，首先想到什么？ 拆点，状压，容斥。
如果我们使用拆点的方法，这道题就与上一题没有什么区别了。我们将每个点拆成 5 个点 i1,i2,i3,i4,i5 , 从 i1 到 i2，从 i2 到 i3 ，.... , 都有一条长度为一的边。如果从点 i 到点 j 有一条 长度为 3 的边，那么我们就从 i3 向 j1 连一条长度为一的边，这样就把长度不一的边全部转化为了长度为 1 的边。
刷题：
Bzoj1009 GT考试
Bzoj2165 大楼
Bzoj1875 HH去散步
Bzoj2004 公交线路
（2）单调队列优化DP
单调队列：
单调队列是一种特殊的队列，可以在队首删除元素，在队首删除和添加元素，维护队列中的元素始终单调。可以视为一段是队列，一段是栈。可以用来维护当前可用区间的最优值。若要维护 一个可用区间内的最小值，那么在添加新元素 x 之前，先从队尾开始，如果队尾元素比 x 大，就将队尾元素弹出，重复此操作，直到队尾元素比 x 小为止，然后再将 x 压入队尾。当队首 元素从可用区间中脱离，变得不可用，就将它从队首删除。始终维护队首元素是当前可用区间的最优值。
例题： POJ 2823 Sliding Window
单调队列优化DP ：
Evensgn的OI学习笔记（一）——动态规划及其优化
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。