标签：begin end max vmatrix inf 动态 规划 dp

前置知识

树剖

传送门

广义矩乘

考虑矩乘大概是一个 \(\sum a\times b\) 的形式，那么考虑把它换成其他东西比如 \(\prod a\&b\) 或者 \(\max a+b\)，其实发现它们都可以用矩乘的理论优化，从另一个角度上讲 floyd 也是矩乘。

定义

数据结构维护带修改的 dp，最常用的大概是线段树。

当然能维护的东西当然只有矩阵了，所以还是做不到太灵活。

模板

以小白逛公园为例，之前学过直接维护最大子段和的线段树方法，但是其实也可以当成一道 dp 来做。

不妨假设没有修改，询问是全局的最大子段和，那么就是一个简单的 dp 问题：\(f_i\) 表示以第 \(i\) 个元素结尾的最大子段和，有 \(f_i=\max(f_{i-1},a_i)\)。

考虑 \(g_i\) 表示 \(\max\limits_{j\le i}f_j\) 则有 \(ans=g_n,g_i=\max(g_{i-1},f_i)\)。

然而我们的目标是让它支持区间查询，所以考虑搬到矩阵上：\(g_i=\max(g_{i-1},f_{i-1},a_i)\)。

则可以列出一个矩阵：

\[\begin{vmatrix}f_{i-1}&g_{i-1}&0\end{vmatrix}\times\begin{vmatrix}a_i&a_i&-\inf\\-\inf&0&-\inf\\a_i&a_i&0\end{vmatrix}=\begin{vmatrix}f_i&g_i&0\end{vmatrix} \]

然后就可以随便维护了。

例题

树上最大权独立集

传送门

考虑先写出 dp 式子：\(f_{u,0/1}\) 表示在 \(u\) 子树里面选点且选/不选 \(u\) 的最大值，有 \(f_{u,0}=\sum \max(f_{v,0},f_{v,1}),f_{u,1}=a_u+\sum f_{v,0}\)。

接下来考虑如何维护，可以想到使用树链剖分，考虑如何使用树链剖分的性质，然后想到设方程 \(g_{u,0/1}\) 表示和 \(f\) 性质相同但是不考虑重儿子的 dp 值，不妨设 \(v\) 为 \(u\) 的重儿子，可以得到以下 dp 式子：

1. \(f_{u,0}=g_{u,0}+\max(f_{v,0},f_{v,1})\)。

2. \(f_{u,1}=g_{u,1}+f_{v,0}\)。

转化为以下的矩阵：

\[\begin{vmatrix}f_{v,0}&f_{v,1}\end{vmatrix}\times \begin{vmatrix}g_{u,0}&g_{u,1}\\g_{u,0}&-\inf\end{vmatrix}=\begin{vmatrix}f_{u,0}&f_{u,1}\end{vmatrix} \]

然后发现一个性质就是只有轻边的 \(g\) 会受到修改的影响，而一次修改最多影响 \(\log\) 个点，所以复杂度是 \(O(\log^2)\) 带大常。

标签：begin,end,max,vmatrix,inf,动态,规划,dp
From： https://www.cnblogs.com/Judgelight/p/17687304.html