做网站东莞东莞建网站,wordpress重新,六安马昌友,张店区创业孵化中心有做网站的吗动态DP入门线性动态DP 前言核心思想例1例22024牛客寒假4K2022牛客寒假2J结论 前言
OI-WiKi上有一个动态DP讲解#xff0c;直接讲到了树型DP领域#xff0c;同时需要树链剖分#xff0c;门槛有点高。本文针对线性DP做一个动态DP的讲解。
首先当然要懂得一定的DP的相关… 动态DP入门线性动态DP 前言核心思想例1例22024牛客寒假4K2022牛客寒假2J结论 前言
OI-WiKi上有一个动态DP讲解直接讲到了树型DP领域同时需要树链剖分门槛有点高。本文针对线性DP做一个动态DP的讲解。
首先当然要懂得一定的DP的相关知识然后需要知道DP方程的矩阵表达。可以看这里——根据递推公式构造系数矩阵用于快速幂。很多DP的状态转移方程都可以写成矩阵形式由此就有了矩阵快速幂优化和动态DP的基础。特别是本文专门举例的线性DP。
核心思想
常规的DP方程一般形如 D i f ( D i − 1 ) D_if(D_{i-1}) Dif(Di−1)
即 D i D_i Di是 D i − 1 D_{i-1} Di−1的某个函数。与矩阵快速幂优化类似想办法将DP方程改为 [ D i 0 或 1 ] M i × [ D i − 1 0 或 1 ] \begin{bmatrix} D_i \\ 0或1 \end{bmatrix}M_i\times\begin{bmatrix} D_{i-1} \\ 0或1 \end{bmatrix} [Di0或1]Mi×[Di−10或1]
其中 M i M_i Mi表示 i i i位置的系数矩阵。这里用到了矩阵乘法不过不一定是乘法只是类乘操作而已即满足某种性质的操作。令上述包含 D i D_i Di的向量记为 X i X_i Xi则方程改为 X i ∏ j 1 i M j × X 0 X_i\prod_{j1}^{i}{M_j}\times{X_0} Xij1∏iMj×X0
于是求 X i X_i Xi转化为区间矩阵求积的操作这个区间操作可以使用线段树维护。同时很自然的也就支持了修改操作。
例1
首先看一个完全不需要动态DP的例子。给定一个数组单点修改区间求和。
规划方程: D i A i D i − 1 D_iA_{i}D_{i-1} DiAiDi−1
写成矩阵形式 [ D i 1 ] [ 1 A i 0 1 ] × [ D i − 1 1 ] \begin{bmatrix} D_i \\ 1 \end{bmatrix}\begin{bmatrix} 1 A_i \\ 0 1 \end{bmatrix}\times\begin{bmatrix} D_{i-1} \\ 1 \end{bmatrix} [Di1][10Ai1]×[Di−11]
因此第 i i i个系数矩阵就是 [ 1 A i 0 1 ] \begin{bmatrix} 1 A_i \\ 0 1 \end{bmatrix} [10Ai1]
而且此处用的就是正常的矩阵乘法。用线段树可以轻松维护其区间积与单点修改操作修改某个点 A i A_i Ai就是修改第 i i i个系数矩阵。对于区间查询 [ l , r ] [l,r] [l,r]只需要计算: a n s ( ∏ i l r [ 1 A i 0 1 ] ) × [ 0 1 ] ans\big(\prod_{il}^{r}\begin{bmatrix} 1 A_i \\ 0 1 \end{bmatrix}\big)\times\begin{bmatrix} 0 \\ 1 \end{bmatrix} ans(il∏r[10Ai1])×[01] 即可 a n s [ 1 ] ans[1] ans[1]即答案。 当然如果进一步推敲的话可以发现这个线段树本质上就是维护的 A i A_i Ai的和。这是一个实现上毫无必要的、但很好的仅供学习的例子如果后面的例子有难度的话。
例2
再看一个复杂一点点的例子。给定一个数组查询区间最大子段和单点修改。首先这个问题仍然可以直接使用线段树解决。其次来看看动态DP的做法。
令 U i U_i Ui是以 i i i结尾的最大子段和 V i V_i Vi是 [ 1 , i ] [1,i] [1,i]区间的最大子段和则规划方程是 U i max ( A i , A i U i − 1 ) V i max ( U i , V i − 1 ) U_i\max{(A_i,A_{i}U_{i-1})} \\ V_i\max{(U_i, V_{i-1})} Uimax(Ai,AiUi−1)Vimax(Ui,Vi−1)
首先修改其中一个DP方程为 V i max ( A i , A i U i − 1 , V i − 1 ) V_i\max{(A_i,A_{i}U_{i-1},V_{i-1})} Vimax(Ai,AiUi−1,Vi−1)
然后写成矩阵形式 [ U i V i 0 ] [ A i − ∞ A i A i 0 A i − ∞ − ∞ 0 ] × [ U i − 1 V i − 1 0 ] \begin{bmatrix} U_i \\ V_i \\ 0 \end{bmatrix}\begin{bmatrix} A_i -\infty A_i \\ A_i 0 A_i \\ -\infty -\infty 0 \end{bmatrix}\times\begin{bmatrix} U_{i-1} \\ V_{i-1} \\ 0 \end{bmatrix} UiVi0 AiAi−∞−∞0−∞AiAi0 × Ui−1Vi−10
这里的 × \times ×表示矩阵的类乘操作或者说是矩阵的广义乘法操作定义如下令矩阵 C A × B CA\times{B} CA×B则 C i , j max k 1 3 ( A i , k B k , j ) C_{i,j}\max_{k1}^{3}{(A_{i,k}B_{k,j})} Ci,jk1max3(Ai,kBk,j)
写成单行、单列的形式即 [ a 1 a 2 a 3 ] × [ b 1 b 2 b 3 ] max ( a 1 b 1 , a 2 b 2 , a 3 b 3 ) \begin{bmatrix}a_1 a_2 a_3\end{bmatrix}\times\begin{bmatrix} b_1 \\ b_2 \\ b_3 \end{bmatrix}\max{(a_1b_1,a_2b_2,a_3b_3)} [a1a2a3]× b1b2b3 max(a1b1,a2b2,a3b3)
因此 [ A i − ∞ A i A i 0 A i − ∞ − ∞ 0 ] \begin{bmatrix} A_i -\infty A_i \\ A_i 0 A_i \\ -\infty -\infty 0 \end{bmatrix} AiAi−∞−∞0−∞AiAi0 就是第 i i i个矩阵一共要维护 N N N个矩阵。修改操作也很容易维护改变 A i A_i Ai就是改变第 i i i个矩阵。区间查询操作 [ l , r ] [l,r] [l,r]就是计算 a n s ( ∏ i l r [ A i − ∞ A i A i 0 A i − ∞ − ∞ 0 ] ) × [ − ∞ − ∞ 0 ] ans\big(\prod_{il}^{r}\begin{bmatrix} A_i -\infty A_i \\ A_i 0 A_i \\ -\infty -\infty 0 \end{bmatrix}\big)\times\begin{bmatrix} -\infty \\ -\infty \\ 0 \end{bmatrix} ans(il∏r AiAi−∞−∞0−∞AiAi0 )× −∞−∞0 a n s [ 1 ] ans[1] ans[1]就是答案因为 a n s [ 1 ] ans[1] ans[1]对应了规划目标 V V V。
2024牛客寒假4K
同样这个题目可以不用动态DP直接用线段树维护相关信息即可。 题目大意给定一个字符串仅包含YBR表示命令。初始位于0位置且右边无边界限制。命令执行如下 Y指令表示在当前位置添加一个块B指令表示先右移一格到达一个新位置再在这个新位置添加一个块R指令表示先将当前位置的块倍增一下再添加一个块假设当前位置本来有3块则该指令过后变成7块。 还有 Q Q Q个操作一共分两类 p c: 将第p个位置的命令改为cs e: 从零开始依次执行 [ s , e ] [s,e] [s,e]区间的命令问最后的块数。 对每个操作2输出答案。 令 D i D_i Di是第 i i i个操作后当前位置的块数注意不一定是第 i i i个位置因为一个命令不一定新增一个位置不过这个并没有影响。令 S i S_i Si是第 i i i个操作后总块数。令动态规划的列向量是: [ D i S i 1 ] \begin{bmatrix} D_{i} \\ S_{i} \\ 1 \end{bmatrix} DiSi1 简单推理一下就可以得到YBR三个命令分别对应的三个系数矩阵是 [ 1 0 1 0 1 1 0 0 1 ] , [ 0 0 1 0 1 1 0 0 1 ] , [ 2 0 1 1 1 1 0 0 1 ] \begin{bmatrix} 1 0 1 \\ 0 1 1 \\ 0 0 1 \end{bmatrix}, \begin{bmatrix} 0 0 1 \\ 0 1 1 \\ 0 0 1 \end{bmatrix}, \begin{bmatrix} 2 0 1 \\ 1 1 1 \\ 0 0 1 \end{bmatrix} 100010111 , 000010111 , 210010111
因此可以得到一个矩阵的数组维护这个矩阵数组的区间积就行支持单点修改。这里用到的就是正经的矩阵乘法。当然这里会注意到系数矩阵连乘展开以后其实是倒序的。前面的两个例子之所以没有这个问题是因为例1中的矩阵形式比较特殊因此支持乘法的交换律。而例2中的操作本身就支持交换律。所以那个两个例子都可以直接按顺序维护。这个例子则是正经的矩阵乘法不支持交换律。因此倒过来维护即可。
2022牛客寒假2J 题目大意有三种魔法球、十种技能每种技能都是三种魔法球的组合可重复。现在需要连续释放技能但是手中只能持有三个魔法球且必须按照队列性质。 例如需要连续释放技能1和2则首先持有三个魔法球记作 a1 a2 a3 释放技能1。随后如果a1a2a3不是技能2的组合则必须先拿掉a1, 追加a4可以自由选择追加的魔法球。 此时手中持有变为了a2a3a4 如果能满足施法即可完成。 否则必须扔掉a2追加a5。 还不行的话就扔掉a3追加a6。此时必然可以释放技能2。 手中持有必须按顺序但是技能构成无需按顺序。 例如假设输入给定技能1的构成是a3a2a1则手中持有a1a2a3一样可以释放技能1 现在给定N个技能的序列两种操作 s e: 问连续释放[s, e]区间内的技能最少需要依次拿几个魔法球每次施法之初手中都是空的p x: 将第p个位置的技能修改为x 首先释放第一个技能必须拿3个球然后考虑后续。 从技能a到技能b需要追加的球的数量显然与a魔法球以及b魔法球的排列有关。 一个技能最多可能存在6种不同的排列。 因此令 D i , j , u , v D_{i,j,u,v} Di,j,u,v 记录技能 i i i的排列 u u u后面跟技能 j j j的排列 v v v时需要改变的魔法球的数量。 所以D是一个 10 × 10 × 6 × 6 10\times10\times6\times6 10×10×6×6的四维数组可以预处理出来。
再考虑一段连续的释放首先考虑 [ 1... n ] [1...n] [1...n]令 Z n u Z_{nu} Znu表示从1释放到 n n n的最少数量且以 n n n的 u u u排列结尾。 则 Z n u min { Z n − 1 , v D n − 1 , n , v , u , v 是 n − 1 的所有排列状态 } Z_{nu} \min\{Z_{n-1,v} D_{n-1,n,v,u}, v是n-1的所有排列状态\} Znumin{Zn−1,vDn−1,n,v,u,v是n−1的所有排列状态} 则 min { Z n u , u 是 n 的所有排列 } \min\{Z_{nu}, u是n的所有排列\} min{Znu,u是n的所有排列}为所求。 将 Z n Z_n Zn看作是列向量将 D i j D_{ij} Dij看做是矩阵可以将规划方程写成矩阵形式 Z n D n − 1 , n × Z n − 1 Z_n D_{n-1,n}\times{Z_{n - 1}} ZnDn−1,n×Zn−1
同样这里是用的是类乘操作与例2中类似只不过这里取的是最小值。同时注意到这个操作是支持交换律的因此按正序维护即可。
题目给定了 N N N个技能则一共需要 N − 1 N-1 N−1次转换因此维护 N − 1 N-1 N−1个矩阵即可。
结论
感觉上线性动态DP是不需要的因为似乎可以直接设计线段树维护相关信息完成。不过从线性DP入手动态DP不失为一个好的学习路线。另一方面动态DP可以提供一个统一的模板构思简单实现高度一致在常数时间充足的情况下值得一试。
