动态 DP（DDP） 笔记

$$\text{WARNING：这玩意我不会讲，慎入！}$$

结合矩阵运算 / 重链剖分，解决一类待修改的树上 DP 问题。

一、前置知识

熟练掌握矩乘优化 DP，会树剖。

知道矩阵乘法没有交换律。

二、广义矩乘

普通的 $(+,\times )$ 矩乘：

$$C_{i,j}=\sum (A_{i,k}\times B_{k,j})$$

常见的广义矩乘有 $(min,+)$，$(max,+)$ 等，如：

$$C_{i,j}=min(A_{i,k}+B_{k,j})$$

具有和矩乘一样的性质，证明见网络。

模板

P4719 【模板】动态 DP。

选若干个没有直接相连的点，使得选择的点权最大。

考虑没修改怎么做。

设 $f_{u,0/1}$ 表示不选 / 选 $u$ 号点，转移显然是 $f_{u,0}=\sum max(f_{v,0},f_{v,1}),f_{u,1}=(\sum f_{v,0})+a_u$。

由于动态 DP 和树剖相关，考虑用树剖的思路改善转移方程。