省选-动态规划-动态 DP · Zhl2010 第二博客

首先肯定是按照 $W$ 排序，然后只有相邻的物品是可能选的。

f_i = \begin{cases} f_{i-1}+a_i & w_i-w_{i-1}>d \\ \min(f_{i-1}+a_i,f_{i-2}+b_{i-1}+b_i) & w_i-w_{i-1}\le d\\ \min(f_{i-1}+a_i,f_{i-2}+b_{i-1}+b_i,f_{i-3}+b_{i-2}+a_{i-1}+b_i) & w_i-w_{i-2}\le d \\ \end{cases}

这玩意儿我们可以用矩阵乘法去维护。我们重新弄一个矩阵乘法表示 c.a[i][j]=min(c.a[i][j],a.a[i][k]+b.a[k][j]);。

矩阵

\begin{bmatrix} a_i & +\infty & +\infty \\ 0 & +\infty & +\infty \\ +\infty & 0 & +\infty \end{bmatrix} \begin{bmatrix} f_{i-1} \\ f_{i-2} \\ f_{i-3} \end{bmatrix} = \begin{bmatrix} f_i = f_{i-1}+a_i \\ f_{i-1} \\ f_{i-2} \end{bmatrix}

\begin{bmatrix} a_i & b_i+b_{i-1} & +\infty \\ 0 & +\infty & +\infty \\ +\infty & 0 & +\infty \end{bmatrix} \begin{bmatrix} f_{i-1} \\ f_{i-2} \\ f_{i-3} \end{bmatrix} = \begin{bmatrix} f_i-\min(f_{i-1}+a_i,f_{i-2}+b_i-1+b_i) \\ f_{i-1} \\ f_{i-2} \end{bmatrix}

\begin{bmatrix} a_i & b_i+b_{i-1} & b_i+a_{i-1}+b_{i-2} \\ 0 & +\infty & +\infty \\ +\infty & 0 & +\infty \end{bmatrix} \begin{bmatrix} f_{i-1} \\ f_{i-2} \\ f_{i-3} \end{bmatrix} = \begin{bmatrix} f_i=\min(f_{i-1}+a_i,f_{i-2}+b_{i-1}+b_i,f_{i-3}+b_{i-2}+a_{i-1}+b_i) \\ f_{i-1} \\ f_{i-2} \end{bmatrix}

然后矩阵的维护就直接用线段树修改+查询了。

有 $m$ 次操作，每次操作给定 $x,y$ ，表示修改点 $x$ 的权值为 $y$ 。你需要在每次操作之后求出这棵树的最大权独立集的权值大小。

首先肯定是 dp，普通的 dp 是：

f_{i,1}=\sum f_{v,0}\\ f_{i,0}=\sum \max(f_{v,0},f_{v,1})

我们发现如果修改一个点，它的贡献将会一直上传，所以...我们可以尝试树链剖分，保证轻边的条数在 $\log$ 级别。

我们设 $g$ 表示只考虑轻儿子。

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

我们需要把这个转化成矩阵乘法，也是自定义 $\oplus$ 是求 $\max$ 。

\begin{vmatrix} f_{i, 0} \\ f_{i, 1} \end{vmatrix} = \begin{vmatrix} g_{i, 0} & g_{i, 0} \\ g_{i, 1} & -\infty \end{vmatrix} * \begin{vmatrix} f_{j, 0} \\ f_{j, 1} \end{vmatrix}

然后我们每一次修改一个点就可以直接改，上传到重链顶端，然后一直向上跳。