前言
受到NOIP的影响，大家都开始学习动态dp，博主比较菜，学的比较晚，以下的学习笔记主要是配合例题和代码讲解。
例题
例题一 【模板】动态dp
题目大意
给定一个$n$个点的树，每个点有点权$a[i]$。
有$m$次修改操作，每次操作给定$x,y$表示将$a[x]$修改为$y$
你需要每次修改后找出若干个点，使得这些点互不相邻，并且点权和最大。
$ n,m\le 1e5$
分析
- 首先考虑不带修的情况，我们令$f[i][1]$表示以i为根的子树，选了i这个的点最大点权，$f[i][0]$表示不选i这个点时的最大点权和。
我们以$u\to v$表示v是u的字节点
考虑转移$f[u][1]=a[u]+\sum_{u\to v}f[v][0],f[u][0]=\sum_{u\to v}Max(f[v][0],f[v][1])$
应该非常显然，不做赘述。 - 现在我们考虑要支持修改了。
先树链剖分，以$son[u]$表示u的重儿子，那么原来的转移方程可以变为
$f[u][1]=a[u]+\sum_{u\to v,v\ne son[u]}f[v][0]+f[son[u]][0]$
$f[u][0]=\sum_{u\to v,v\ne son[u]}Max(f[v][0],f[v][1])+Max(f[son[u]][0],f[son[u]][1])$
我们令
$g[u][0]=\sum_{u\to v,v\ne son[u]}Max(f[v][0],f[v][1])$
$g[u][1]=a[u]+\sum_{u\to v,v\ne son[u]}f[v][0]$
也就是f中除了重儿子的部分
那么我们的dp就可以化为
$f[u][1]=g[u][1]+f[son[u]][0]$
$f[u][0]=g[u][0]+Max(f[son[u]][0],f[son[u]][1])$
再用矩阵来描述每一次转移
把矩阵乘法重新定义一下。
$c[i][j]=\sum_{k=1}^{n}a[i][k]*b[k][j] \to c[i][j]=Max(a[i][k]+a[k][j])$
这样的矩阵乘法也是满足结合律的假装是吧，博主也不会证
那么重儿子上的信息每次在线段树上查询，轻儿子的信息直接暴力维护。
每次修改一个点。
(1)先将自己的矩阵改掉
(2)跳到重链顶端，暴力修改重链顶端的父亲的矩阵
(3)跳到重链顶端的父亲
重复步骤(1)(2)(3)直至跳到节点0
由于最多跳log条重链，每次修改前要线段树上查询我的f值，所以修改一次的总复杂度是$log^2$的。
查询的复杂度为$log$，所以总复杂度为$n*log^2(n)$代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
using namespace std;
int n,m,tot,cnt,x,y;
int a[N],son[N],tow[N<<1],nxt[N<<1],head[N],size[N],dep[N],top[N],down[N],dfn[N],g[N][2],f[N][2],fnd[N],fa[N];
template <typename T> void read(T&t) {
t=0;
bool fl=true;
char p=getchar();
while (!isdigit(p)) {
if (p=='-') fl=false;
p=getchar();
}
do {
(t*=10)+=p-48;p=getchar();
}while (isdigit(p));
if (!fl) t=-t;
}
inline void add(int x,int y){
tow[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
void dfs(int u){
f[u][0]=0;
f[u][1]=a[u];
size[u]=1;
for (int p=head[u];p;p=nxt[p]){
int v=tow[p];
if (v!=fa[u]){
fa[v]=u;
dfs(v);
f[u][0]+=max(f[v][0],f[v][1]);
f[u][1]+=f[v][0];
size[u]+=size[v];
if (size[v]>size[son[u]]) son[u]=v;
}
}
}
void dfs1(int u,int f){
dfn[u]=++cnt;
fnd[cnt]=u;
top[u]=f;
down[f]=dfn[u];
if (son[u]) dfs1(son[u],f);
for (int p=head[u];p;p=nxt[p]){
int v=tow[p];
if (v!=fa[u]&&v!=son[u]) dfs1(v,v);
}
}
struct matrix{
int a[2][2];
inline matrix(){memset(a,0,sizeof(a));};
inline matrix(int x,int y){a[0][0]=a[0][1]=x,a[1][0]=y,a[1][1]=-1e9;}
inline matrix operator * (const matrix &t) const{
matrix ret;
for (int i=0;i<=1;i++){
for (int j=0;j<=1;j++){
ret.a[i][j]=max(a[i][0]+t.a[0][j],a[i][1]+t.a[1][j]);
}
}
return ret;
}
};
void dfs2(int u){
g[u][1]=a[u];
g[u][0]=0;
for (int p=head[u];p;p=nxt[p]){
int v=tow[p];
if (v!=son[u]&&v!=fa[u]){
dfs2(v);
g[u][0]+=max(f[v][0],f[v][1]);
g[u][1]+=f[v][0];
}
}
if (son[u]) dfs2(son[u]);
}
struct node{
int l,r;
matrix data;
}T[N<<2];
void build(int u,int l,int r){
T[u].l=l,T[u].r=r;
if (l==r){
T[u].data=matrix(g[fnd[l]][0],g[fnd[l]][1]);
return;
}
int mid=l+r>>1,v=u<<1;
build(v,l,mid);
build(v|1,mid+1,r);
T[u].data=T[v].data*T[v|1].data;
}
void modify(int u,int op){
if (T[u].l==T[u].r){
T[u].data=matrix(g[fnd[op]][0],g[fnd[op]][1]);
return;
}
int mid=T[u].l+T[u].r>>1,v=u<<1;
if (op<=mid) modify(v,op);
else modify(v|1,op);
T[u].data=T[v].data*T[v|1].data;
}
matrix query(int u,int L,int R){
if (L<=T[u].l&&T[u].r<=R) return T[u].data;
int mid=T[u].l+T[u].r>>1,v=u<<1;
if (R<=mid) return query(v,L,R);
if (L>mid) return query(v|1,L,R);
return query(v,L,R)*query(v|1,L,R);
}
int main(){
read(n),read(m);
for (int i=1;i<=n;i++) read(a[i]);
for (int i=1;i<n;i++){
read(x),read(y);
add(x,y),add(y,x);
}
dfs(1);
dfs1(1,1);
dfs2(1);
build(1,1,n);
for (int i=1;i<=m;i++){
read(x),read(y);
g[x][1]+=y-a[x];
a[x]=y;
while (x){
modify(1,dfn[x]);
x=top[x];
matrix tmp=query(1,dfn[x],down[x]);
int ff=fa[x];
g[ff][0]-=max(f[x][0],f[x][1]);
g[ff][1]-=f[x][0];
f[x][0]=tmp.a[0][0];
f[x][1]=tmp.a[1][0];
g[ff][0]+=max(f[x][0],f[x][1]);
g[ff][1]+=f[x][0];
x=fa[x];
}
printf("%d\n",max(f[1][0],f[1][1]));
}
return 0;
}
例题二 动态dp【加强版】
题目大意
和例题一一样，只不过强制在线，并且$n,m\le 1e6$
分析
好像树剖跑不过去了，那么我们考虑用lct来代替树剖，复杂度确实是少了一个log，但是实际表现不理想，lct还是常数太大了。
实际上我们用不到access,change_root,link,cut等操作，那我们是不是可以考虑构造一种类似的数据结构呢。
全局平衡二叉树闪亮登场。
全局平衡二叉树
概述
与lct类似，把每条重链用一棵辅助树来维护，辅助树之间用虚边相连，每个节点维护自己所在重链辅助树的子树矩阵的乘积。如果会lct的话比较好理解。
建树
我们定义每个点的权重$fs[u]=size[u]-size[fs[u]]$，对于每条重链，每次找到带权重心，左右递归建树即可，深度比我小的点在左儿子，深度比我大的点在右儿子。
复杂度证明
可以参考 杨哲《SPOJ375 QTREE 解法的一些研究》
代码
这里直接贴出全体的代码，建树的代码也包括在其中。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
using namespace std;
int n,x,y,tot,top,lastans,root,m;
int a[N],tow[N<<1],son[N],nxt[N<<1],head[N],size[N],fs[N],fa[N],Fa[N],st[N],ch[N][2];
bool kill[N];
template <typename T> void read(T&t) {
t=0;
bool fl=true;
char p=getchar();
while (!isdigit(p)) {
if (p=='-') fl=false;
p=getchar();
}
do {
(t*=10)+=p-48;p=getchar();
}while (isdigit(p));
if (!fl) t=-t;
}
inline void add(int x,int y){
tow[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
void dfs(int u){
size[u]=1;
for (int p=head[u];p;p=nxt[p]){
int v=tow[p];
if (v!=fa[u]){
fa[v]=u;
dfs(v);
size[u]+=size[v];
if (size[v]>size[son[u]]) son[u]=v;
}
}
fs[u]=size[u]-size[son[u]];
}
struct matrix{
int a[2][2];
inline matrix(){a[0][0]=a[0][1]=a[1][0]=a[1][1]=-1e9;}
inline matrix operator * (const matrix &t) const{
matrix ret;
for (int i=0;i<=1;i++){
for (int j=0;j<=1;j++){
ret.a[i][j]=max(a[i][0]+t.a[0][j],a[i][1]+t.a[1][j]);
}
}
return ret;
}
inline int mx(){
return max(max(a[0][0],a[1][0]),max(a[0][1],a[1][1]));
}
inline void add(int x,int y){
a[0][0]+=x,a[0][1]+=x,a[1][0]+=y;
}
}T[N],sum[N];
void update(int u,int f){
Fa[u]=f;
kill[u]=1;
T[f].add(sum[u].mx(),max(sum[u].a[0][0],sum[u].a[0][1]));
}
void pushup(int u){
sum[u]=sum[ch[u][0]]*T[u]*sum[ch[u][1]];
}
int sbuild(int l,int r){
if (l>r) return 0;
int tt=0,tmp=0;
for (int i=l;i<=r;i++) tt+=fs[st[i]];
for (int i=l;i<=r;i++){
tmp+=fs[st[i]];
if (tmp>=(tt>>1)){
Fa[ch[st[i]][0]=sbuild(l,i-1)]=st[i];
Fa[ch[st[i]][1]=sbuild(i+1,r)]=st[i];
pushup(st[i]);
return st[i];
}
}
}
int build(int u){
for (int i=u;i;i=son[i]){
for (int p=head[i];p;p=nxt[p]){
int v=tow[p];
if (v!=fa[i]&&v!=son[i]){
int kk=build(v);
update(kk,i);
}
}
}
top=0;
for (int i=u;i;i=son[i]) st[++top]=i;
return sbuild(1,top);
}
void modify(int u,int data){
T[u].a[1][0]+=data-a[u];
a[u]=data;
while (u){
if (kill[u]){
int t1=sum[u].mx(),t2=max(sum[u].a[0][0],sum[u].a[0][1]);
pushup(u);
T[Fa[u]].add(sum[u].mx()-t1,max(sum[u].a[0][0],sum[u].a[0][1])-t2);
}
else{
pushup(u);
}
u=Fa[u];
}
}
int main(){
read(n),read(m);
for (int i=1;i<=n;i++) read(a[i]);
T[0].a[0][0]=T[0].a[1][1]=0;
sum[0].a[0][0]=sum[0].a[1][1]=0;
for (int i=1;i<=n;i++){
T[i].a[1][0]=a[i];
T[i].a[0][0]=T[i].a[0][1]=0;
}
for (int i=1;i<n;i++){
read(x),read(y);
add(x,y);
add(y,x);
}
dfs(1);
root=build(1);
while (m--){
read(x),read(y);
modify(x,y);
lastans=sum[root].mx();
printf("%d\n",lastans);
}
return 0;
}
例题三 洪水
题目大意
给定一颗n个点的树，每个点有点权。
给m次操作，操作分成两类。
(1)修改操作，修改一个点的点权
(2)询问操作，对于一个节点，删除若干个点，使得询问的点与其子树中所有叶子均不连通，回答删除点的最小权值和
$n,m \le 2e5$
分析
我们与例题一类似考虑，先考虑不带修改的情况。
以$f[u]$表示使得u与其子树中所有叶子节点不连通的最小删除点权和。
我们以$u\to v$表示v是u的字节点
转移$f[u]=Min(a[u],\sum_{u\to v}f[v])$
以$son[u]$表示u的重儿子。
$f[u]=Min(a[u],f[son[v]]+\sum_{u\to v,v\ne son[u]}f[v])$
令
$g[u]=\sum_{u\to v,v\ne son[u]}f[v]$
与例题一一样重新定义一下矩阵乘法，加法变为取max，乘法变为加法
那么有
博主手推，可能不是很优秀
剩下的就和例题一一样了。
但是要注意一个问题，询问的时候还需要查询每个几点的f值，并不是只有根节点的。
对于一个节点的dp值，应该是这条重链上所有深度大于等于他的矩阵的乘积，(当我们查询根节点的时候，一定是整颗子树)，由于全局平衡二叉树的深度满足二叉查找树，所以我们在每次向上跳的过程中，如果我是从左儿子上去的，那么要把我父亲及父亲的整个右子树都乘上来，如果从右儿子上去则不用乘。
代码
1 |
|
例题四 [SDOI2017]切树游戏
链接
txc大爷的博客
写的非常的好
结语
动态dp的套路实际上都一样。
核心内容就在于先推出不带修改时的dp方程，再将dp方程中重儿子的信息分离出来，用矩阵来表示转移。
树链剖分后，重儿子的信息用线段树维护，轻儿子的信息暴力修改即可，由于树剖的优秀性质，
跳上去的过程中最多暴力修改log次，复杂度就是对的，再利用全局平衡二叉树可以使复杂度更优。
以上就是博主对动态dp的个人理解，如果有写的不对的地方，欢迎在评论中指出，感激不尽。