矩阵乘法和动态dp

矩阵乘法

\begin{aligned} c_{i,j}&=\min_{k=1}^d(a_{i,k}+b_{k,j})\\ c_{i,j}&=\sum_{k=1}^d\max(a_{i,k},b_{k,j}) \end{aligned}

只有结合律。

无交换律

但是有一些有交换律，但是一定得证明。

$O(T^3\log n)$

权值不是为 $1$ ，分层最短路，矩阵解决。

针对矩阵乘的是不一样的，并且多次询问 $dp$ 值，线段树保存一段矩阵的连乘，快速求解。

f_i=v_i+\sum_{j=1}^{l_i} w_{i,j} \times f_{i-j}

构造矩阵求解。

$f_i$ 表示以 $i$ 结尾的最大子段和。

$g_i$ 表示前 $i$ 个最大子段和。
$f_i=\max(f_{i-1}+a_i,a+i)$

$g_i=max(f_i,g_{i-1})$

广义矩阵乘法。

c_{i,j}=\min_{k=1}^d(a_{i,k}+b_{k,j})

\begin{bmatrix} g_i& f_i &0 \end{bmatrix}= \begin{bmatrix} g_{i-1}&f_{i-1}&0 \end{bmatrix}\times \begin{bmatrix} 0& -\infty &-\infty\\ a_i&a_i&-\infty\\ a_i&a_i&0\\ \end{bmatrix}\dotsb

线段树维护。

带修求树的最大权独立集。

考虑树上的操作变为序列上的操作，维护重儿子，轻儿子信息。

本质是为了减小矩阵大小。

第一遍求出答案，将矩阵算上。

从叶子节点，左乘矩阵求结果。

轻儿子

g_{i,0}=\sum_{j\in son_i,j\not ={ws}} \max(f_{j,0},f_{j,1})

g_{i,1}=(\sum_{j\in son_i,j\not ={ws}}f_{j,0})+v_i

答案

f_{i,0}=\max(g_{i,0}+f_{ws,0},g_{i,0}+f_{ws,1})

f_{i,1}=g_{i,1}+f_{ws,0}

叶子节点初始化 $f_{i,0}=g_{i,0}=g_{i,1}=0$ ， $f_{i,1}=v_i,$

\begin{bmatrix} f_{i,0}\\ f_{i,1} \end{bmatrix}= \begin{bmatrix} g_{i,0}&g_{i,0}\\ g_{i,1} &-\infty \end{bmatrix}\times \begin{bmatrix} f_{ws,0}\\ f_{ws,1} \end{bmatrix}

叶子最后一项为 $0$ ，这样构造和欧拉序同样，方便写代码，每次都是左乘右，因此线段树正常写就好了，每次只改一条链，最后求 $1$ 所在链就行。

树形动态规划，树剖矩阵优化高效解决问题。

大力 $dp$ 线段树维护矩阵。

__END__