Idea
主要指用矩阵维护带修改的 dp 问题的方法，一般会用到数据结构来维护矩阵。
矩阵的用法具体见 矩阵加速优化 dp.
下面主要根据例题讲解。
Problem
1. P4719 【模板】"动态 DP"&动态树分治
如果不带修改，那就是一道经典的树上最大独立集问题。
不妨设 \(f_{i,0/1}\) 表示节点 \(i\) 及其子树内的最大独立集，其中 \(0\) 表示不选节点 \(i\)，\(1\) 表示选节点 \(i\)，则有转移方程：
\[f_{u,0}=\sum_{v\in son_u}\max(f_{v,0},f_{v,1})\\ f_{u,1}=a_u+\sum_{v\in son_u}f_{v,0} \]那带修改怎么做呢？
考虑每修改一个节点的权值，所有该节点到根节点路径上的答案都会发生改变，如果暴力修改显然是不行的。正常情况下，我们一般会选择重链剖分来解决此类问题。
但是问题在于，我们显然是无法通过数据结构快速修改祖先 f 值的，因为这个式子一看就不满足结合律。
所以我们考虑把状态转移方程写成一个满足结合律且将轻重儿子分开转移的矩阵的形式。
我们额外设 \(g_{i,0}\) 表示不选根节点，轻儿子可选可不选时的最大权值，\(g_{i,1}\) 表示选择根节点，轻儿子都不选时的最大权值。则有：
\[g_{u,0}=\sum_{v\in lightson} \max(f_{v,0},f_{v,1})\\ g_{u,1}=a_{u}+\sum_{v\in lightson} f_{v,0} \]此时我们就可以进一步将我们的 \(f\) 数组精简，状态转移方程变为：
\[f_{u,0}=g_{u,0}+\max(f_{heavyson,0},f_{heavyson,1})\\ f_{u,1}=g_{u,1}+f_{heavyson,0} \]这个形式就比较好变成矩阵了嘛。考虑使用 max + 的广义矩阵乘法：
\[C_{i,j}=\max(C_{i,j},A_{i,k}+B_{k,j}) \]由于 max 具有结合律，加法具有对于 max 的分配律，所以该矩阵乘法形式显然成立。设 \(v=heavyson\)，我们现在就是在考虑一个转移矩阵 \(U=\begin{vmatrix}a&b\\c&d\end{vmatrix}\)，满足：
\[|f_{v,0},f_{v,1}|\times U=|f_{u,0},f_{u,1}| \]根据我们定义的矩阵乘法规则，有：
\[f_{u,0}=\max(f_{v,0}+a,f_{v,1}+c)\\ f_{u,1}=\max(f_{v,0}+b,f_{v,1}+d) \]将我们精简之后的 \(f_{u,0}\) 转移方程中 \(g_{u,0}\) 扔进 max 里面，则显然可以得到 \(a=g_{u,0},b=g_{u,1},c=g_{u,0}\)，由于不存在 \(d\) 这一项，所以将其设置为负无穷即可。故：
\[U=\begin{vmatrix}g_{u,0}&g_{u,1}\\g_{u,0}&-inf\end{vmatrix} \]于是我们便得到了具有结合律的转移矩阵！
那么怎么将矩阵和树链剖分相结合呢？注意到重链剖分是有一些很好的性质的，如：
-
每一个节点到达根节点最多跳 \(O(\log n)\) 条重链。
-
每一条重链的末端都为叶子节点，而叶子节点的 \(f\) 数组初始为 \(0\)。
前者保证了链与链之间转移的复杂度，而对于链内，链的顶部节点的转移矩阵显然就是这一条整链的转移矩阵之积（从底部乘到顶部）。
所以考虑线段树每个节点维护一段 dfs 序区间内的转移矩阵乘积，修改一个节点的权值时，我们先改掉该节点的转移矩阵，然后由于我们在写矩阵的时候将轻重儿子分开了，转移矩阵当中只有关于轻儿子的信息，所以对于 \(u,v\) 在一条重链上的情况，若修改了儿子 \(v\)，\(u\) 的转移矩阵依旧是不变的。由此我们便可以有如下流程：
- 修改一个节点的权值，并单点修改该节点在线段树上的矩阵。
- 跳到该节点所在重链的链首，并将这一条链上的积查询，然后将链首的父亲节点的转移矩阵根据该矩阵积更新。
- 重复上述流程，直到到达根节点。
注意由于该矩阵的加法满足可减性，所以更新转移矩阵时可以先查询原转移矩阵答案之积，将其减去后再加上新转移矩阵答案即可更新。
且由于矩阵乘法不满足交换律，且统计时应该从底到顶，而因为深度较深的节点 dfs 序更大，所以需要注意统计矩阵答案时的顺序：线段树 pushup 时要使用右儿子乘左儿子，查询时要先查询右儿子再查询左儿子。最后将最终的转移矩阵乘上向量 \(|0,0|\) 即可得到答案。
代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int INF=1e8;
int n,m,a[N],rk[N];
struct Edge{
int head[N],to[N<<1],next[N<<1],tot;
void adde(int u,int v){
to[++tot]=v,next[tot]=head[u],head[u]=tot;
}
}B;
struct Matrix{
int a[2][2];
Matrix(){
a[0][0]=a[1][1]=a[1][0]=a[0][1]=0;
}
void chan(int x,int b,int c,int d){
a[0][0]=x,a[0][1]=b,a[1][0]=c,a[1][1]=d;
}
}I,Z[N];
Matrix operator *(const Matrix&x,const Matrix&y){
Matrix z;
for (int k=0;k<2;k++)
for (int i=0;i<2;i++)
for (int j=0;j<2;j++)
z.a[i][j]=max(z.a[i][j],x.a[i][k]+y.a[k][j]);
return z;
}
struct Tree{
Matrix t[N<<2];
void build(int i,int l,int r){
if (l==r){
t[i]=Z[rk[l]];
return;
}
int mid=l+r>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
t[i]=t[i<<1|1]*t[i<<1];
}
void chan(int i,int l,int r,int p,Matrix x){
if (l==r){
t[i]=x;
return;
}
int mid=l+r>>1;
if (p<=mid) chan(i<<1,l,mid,p,x);
else chan(i<<1|1,mid+1,r,p,x);
t[i]=t[i<<1|1]*t[i<<1];
}
Matrix query(int i,int l,int r,int ql,int qr){
if (ql<=l&&r<=qr) return t[i];
int mid=l+r>>1;
if (ql>mid) return query(i<<1|1,mid+1,r,ql,qr);
if (qr<=mid) return query(i<<1,l,mid,ql,qr);
return query(i<<1|1,mid+1,r,ql,qr)*query(i<<1,l,mid,ql,qr);
}
}T;
struct CutTree{
int dep[N],fa[N],top[N],zson[N],id[N],cnt,size[N],g[N][2],f[N][2],en[N];
void dfs1(int u){
dep[u]=dep[fa[u]]+1,size[u]=1;
for (int i=B.head[u];i;i=B.next[i]){
int v=B.to[i];
if (v!=fa[u]){
fa[v]=u;
dfs1(v);
size[u]+=size[v];
if (size[v]>size[zson[u]])
zson[u]=v;
}
}
}
void dfs2(int u,int tp){
top[u]=tp,id[u]=++cnt,rk[cnt]=u;
g[u][1]=a[u];
if (zson[u]){
dfs2(zson[u],tp);
f[u][0]=max(f[zson[u]][0],f[zson[u]][1]);
f[u][1]=f[zson[u]][0];
}else en[tp]=u;
for (int i=B.head[u];i;i=B.next[i]){
int v=B.to[i];
if (v!=fa[u]&&v!=zson[u]){
dfs2(v,v);
g[u][0]+=max(f[v][0],f[v][1]);
g[u][1]+=f[v][0];
}
}
f[u][0]+=g[u][0],f[u][1]+=g[u][1];
Z[u].chan(g[u][0],g[u][1],g[u][0],-INF);
}
Matrix modify(int x,int k){
g[x][1]+=k-a[x],a[x]=k;
while (top[x]!=1){
int tp=top[x],ftp=fa[tp];
Matrix la=I*T.query(1,1,n,id[tp],id[en[tp]]);
Z[x].chan(g[x][0],g[x][1],g[x][0],-INF),T.chan(1,1,n,id[x],Z[x]);
Matrix now=I*T.query(1,1,n,id[tp],id[en[tp]]);
g[ftp][1]+=now.a[0][0]-la.a[0][0];
g[ftp][0]+=max(now.a[0][0],now.a[0][1])-max(la.a[0][0],la.a[0][1]);
x=ftp;
}
Z[x].chan(g[x][0],g[x][1],g[x][0],-INF),T.chan(1,1,n,id[x],Z[x]);
Matrix ans=I*T.query(1,1,n,id[1],id[en[1]]);
return ans;
}
}C;
int read(){
int w=0,f=1;
char ch=getchar();
while (ch>'9'||ch<'0') {
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9') {
w=(w<<3)+(w<<1)+(ch^48);
ch=getchar();
}
return w*f;
}
int main(){
n=read(),m=read();
for (int i=1;i<=n;i++) a[i]=read();
for (int i=1;i<n;i++){
int u=read(),v=read();
B.adde(u,v),B.adde(v,u);
}
C.dfs1(1),C.dfs2(1,1);
T.build(1,1,n);
while (m--){
int x=read(),y=read();
Matrix ans=C.modify(x,y);
cout<<max(ans.a[0][0],ans.a[0][1])<<'\n';
}
return 0;
}
2. CF750E New Year and Old Subsequence
好像是什么子序列自动机上 dp。
设 \(dp_{i,0/1/2/3/4}\) 分别表示包含子序列 \(\varnothing\)，子序列 \(2\)，子序列 \(20\)，子序列 \(201\)，子序列 \(2017\) 且不包含之后的子序列以及子序列 \(2016\) 时的方案数。
则根据定义，有线性递推式：
\[dp_{i,0}=dp_{i-1,0}+[a_i=2]\\ dp_{i,1}=\min(dp_{i-1,1}+[a_i=0],dp_{i-1,0}[a_i=2])\\ dp_{i,2}=\min(dp_{i-1,2}+[a_i=1],dp_{i-1,1}[a_i=0])\\ dp_{i,3}=\min(dp_{i-1,3}+[a_i=7|a_i=6],dp_{i-1,2}[a_i=1])\\ dp_{i,4}=\min(dp_{i-1,4}+[a_i=6],dp_{i-1,3}[a_i=7])\\ \]于是可以写成一个 \(5\times 5\) 的矩阵，并使用 min + 的广义矩阵乘法。
此时对于全局，第 \(i\) 个位置的答案矩阵显然就是 \(1\) 到 \(i\) 的所有转移矩阵之积。如此我们便将一个线性转移方程转化为了一个满足结合律的矩阵转移方程。
那对于区间询问呢？对于区间询问，显然只需要用一个数据结构维护区间矩阵乘积即可。
3. P7359 「JZOI-1」旅行
在每个节点时的状态只有两个：有船或是没船。
显然两个点之间的路径可以由起点到 lca 的路径和 lca 到终点的路径拼接起来，所以我们可以考虑设置两个数组 \(dp1_{i,0/1}\) 和 \(dp2_{i,0/1}\) 分别表示从 \(i\) 到 \(i\) 的父亲，当前走路到 \(i\) 或坐船到 \(i\) 的最短时间，以及从 \(i\) 的父亲到 \(i\)，当前走路到 \(i\) 或坐船到 \(i\) 的最短时间。有转移方程：
\[dp1_{fa,0}=\min(dp1_{i,0}+a_p,dp1_{i,1}+a_p)\\ dp1_{fa,1}=\min(dp1_{i,0}+L+a_p+z_p,dp1_{i,1}+a_p+z_p)\\ dp2_{i,0}=\min(dp2_{fa,0}+a_p,dp2_{fa,1}+a_p)\\ dp2_{i,1}=\min(dp2_{fa,0}+L+a_p+z'_p,dp2_{fa,1}+a_p+z'_p) \]为了能迅速求解，不妨将转移方程写成转移矩阵，通过倍增优化求解即可。
转移显然，询问时将两条路径的矩阵拼接起来即可。
这题又一次证明了转移矩阵由于满足结合律而与数据结构拥有的高度适配性。
4. P6573 [BalticOI 2017] Toll
观察到题目中的特殊式子有些怪异，且 \(k\) 又十分小，仔细思考一下，发现其实就相当于是给定了一张每一层节点个数都为 \(k\) 的分层 DAG.
先思考一下朴素的算法应该怎么做：不妨设 \(dp_i\) 表示到达 \(i\) 的最少价钱，则每次询问就需要从 \(a\) 到 \(b\) 跑一边类似于拓扑排序的过程，状态转移方程为：
\[dp_u=\min_{v\to u}(dp_v+t_{v,u}) \]考虑到 \(k\) 十分小，所以我们可以将每一层节点的转移方程压成一个转移矩阵（矩阵相较于普通转移方程，额外满足了结合律）此时我们便可以使用数据结构维护转移矩阵的区间积，此时对于每次询问，我们只需要知道 \(a\) 和 \(b\) 所在的层数，在数据结构中查到转移矩阵，用初始向量与之相乘即可。
时间复杂度 \(O(nk^3+qk^3\log n)\).
注意到瓶颈是在查询，将查询时的矩阵乘矩阵优化为向量乘矩阵可以优化掉一个常数 \(k\)。
5. #3539. 「JOI Open 2018」猫或狗
先考虑怎么静态的计算一个花园的危险程度。
不妨设 \(dp_{i,0/1/2}\) 分别表示在以 \(i\) 为根的子树中，与 \(i\) 联通的小屋中什么宠物都没有或只有狗或只有猫的满足条件的最小阻隔数，则有状态转移方程：
\[dp_{u,0}=([a_i=1|a_i=2]\times\inf)\sum_{v\in son_u}\min(dp_{v,0},dp_{v,1}+1,dp_{v,2}+1)\\ dp_{u,1}=([a_i=1]\times \inf)\sum_{v\in son_u}\min(dp_{v,0},dp_{v,1},dp_{v,2}+1)\\ dp_{u,2}=([a_i=2]\times \inf)\sum_{v\in son_u}\min(dp_{v,0},dp_{v,1}+1,dp_{v,2}) \]观察到 \(dp_0\) 这一维是会被 \(dp_1\) 和 \(dp_2\) 覆盖的，所以我们也可以设 \(dp_{i,1}\) 表示与猫不连通的最小阻隔数，\(dp_{i,2}\) 表示与狗不连通的最小阻隔数，而取消 \(dp_{i,0}\) 的设置，稍微修改一下方程即可转移。
考虑修改一次节点的状态时，就会改变当前节点到达根节点的所有 dp 值。所以考虑使用树链剖分来实现快速修改和转移。
设置矩阵时考虑将转移方程的轻重儿子分开，将轻儿子单独列一个转移方程，变成转移矩阵，按照第一题的套路，树链剖分维护链上转移矩阵即可。
（且轻儿子的转移矩阵外层运算为加，满足可减性，故可以不用线段树维护，改成树上差分也是可以的。）
6. P5024 [NOIP2018 提高组] 保卫王国
先考虑朴素的 dp。设 \(dp_{i,0/1}\) 表示对于以 \(i\) 为根的子树，节点 \(i\) 不驻扎或驻扎军队时的最小花费。则有：
\[dp_{u,0}=\sum_{v\in son_u}dp_{v,1}\\ dp_{u,1}=\sum_{v\in son_u}\min(dp_{v,0},dp_{v,1}) \]而现在加上了多次询问，每次询问都会固定两个节点是否驻扎军队，这是一个动态的过程，考虑将 dp 方程写成矩阵后寻找优化方式。设 \(g_{i,0/1}\) 表示以节点 \(i\) 为根子树中，节点 \(i\) 不选且轻儿子选，以及节点 \(i\) 选且轻儿子可选可不选时的最小花费，则有转移：
\[|dp_{u,0},dp_{u,1}|=|dp_{heavyson,0},dp_{heavyson,1}|\times\begin{vmatrix}\text{inf}&g_{u,1}\\g_{u,0}&g_{u,1}\end{vmatrix} \]那么每次固定两个节点时，相当于就是将它们的转移矩阵中的一些项变成了 inf，也就相当于是作了两次转移矩阵的单点修改。套路树链剖分维护一下，相邻节点都强制不驻扎时无解，否则有解。
Ending
所以我们为什么要用动态 dp 呢？动态 dp 的本质又是什么呢？
动态 dp 可以做的题目一般都是多次询问的，对于每次询问，如果我们的统计方式是满足结合律的，那么就可以使用数据结构快速维护。但可惜我们的线性递推方程是不满足结合律的，如果不采取什么措施，我们就只能重新 dp。所以我们就需要考虑一种和线性递推方程等价且满足结合律的方式来进行转移。
于是我们就想到了矩阵。矩阵显然是满足结合律的，而大多数数据结构都是需要其所维护的东西满足结合律，于是二者一拍集合，联合起来，就变成了动态 dp 。
所以由此个人认为，动态 dp 的本质其实就是矩阵化的状态转移方程与数据结构的有机结合。
标签：min,max,矩阵,转移,优化,节点,dp From： https://www.cnblogs.com/ydtz/p/16777547.html