整个博客的时间都是假的,给文章排号用的.
第一场网络赛
M
题面:给你一个带边权的图,图上还有额外m条特殊边(0花费),但是有使用次数限制:
现在要你求出限制为0-n时从1到所有点的权值最小和
神仙dp题.我们考虑dp表示当前答案,枚举k,一点一点加边.
如何模拟这个过程?假设dp为当前答案数组,每次加边的时候意味着uv两点权值是相同的.
但是为了防止加边传递(也就是出现一步走了好多边的情况),额外设置一个tmp表示当前最大值,用这个值去更新就可以了.
实际写的时候还有一个额外问题:先从根更新子树还是先从子树更新根节点?
答案是:必须先从子树更新根.
考虑这个情况(bc是特殊边):1
2
3a---b--e-f-g
\ /
c-d
先更新子树会导致b节点回传c之后不会再更新d,就会WA.
D
给一棵树,每个点有点权,你现在要把某些边切开(没数量限制),最大化剩下的连通块的极差和.
感觉有很多树形dp的技巧不是能教出来的,必须自己写…
Flu赛时一直在想怎么维护这条链上的最大值最小值,所以到最后也没想出来…
结果赛后翻别人的题解才知道,可以用类似”重力势能”的方法维护单调的链.
我们维护dp[num][3],其中0表示节点num已经被使用了的结果,1表示强制num作为最小值出现的结果,2为强制num作为最大值出现的结果,那么作为最小值出现就有(假设g是所有子树的答案,节点num新开一条链,所以直接减掉或加上就行)1
2
3
4
5
6
7
8for(auto i:vc[num]){
if(i==ko)continue;
dfs(i,num);
g+=dp[i][0];
}
dp[num][0]=g;
dp[num][1]=g-dat[num];//num作为最小值出现
dp[num][2]=g+dat[num];//num作为最大值出现
这个时候我们在尝试把极差(一条单调链上的两端差)断成一条一条单独的边,而不是用dp维护链上的最大最小值.
比如说 1-2-3 这条链,1作为最小值,直接-1即可,2继承自1,当前2作为最大值出现,那么加上2即可.然后这个时候假设2也作为最小值出现的话,再减掉2即可,然后3继承2再加上3,答案就是-1+2-2+3=2.
这么做的好处是在合并链的时候,两条链可以直接权值相加,而不是枚举哪个作为最大值出现.
所以最后的代码长这样,我们的mx1和mx2指定两个最小值,分别是mx1作为最小值出现能带来最大的贡献(dp[num][1]-dp[num][0]最大):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
29void dfs(int num,int ko){
i64 g=0,mx1=0,mx2=0;
for(auto i:vc[num]){
if(i==ko)continue;
dfs(i,num);
g+=dp[i][0];
if(mx1==0||(dp[i][1]-dp[i][0]>dp[mx1][1]-dp[mx1][0])){
mx2=mx1;
mx1=i;
}else if(mx2==0||(dp[i][1]-dp[i][0]>dp[mx2][1]-dp[mx2][0])){
mx2=i;
}
}
dp[num][0]=g;
dp[num][1]=g-dat[num];//num作为最小值出现
dp[num][2]=g+dat[num];//num作为最大值出现
for(auto i:vc[num]){
if(i==ko)continue;
dp[num][1]=max(dp[num][1],g+dp[i][1]-dp[i][0]);
dp[num][2]=max(dp[num][2],g+dp[i][2]-dp[i][0]);
dp[num][0]=max(dp[num][0],g+dat[num]+dp[i][1]-dp[i][0]);
dp[num][0]=max(dp[num][0],g-dat[num]+dp[i][2]-dp[i][0]);
if(i!=mx1){
dp[num][0]=max(dp[num][0],g-dp[i][0]-dp[mx1][0]+dp[mx1][1]+dp[i][2]);
}else if(mx2!=0){
dp[num][0]=max(dp[num][0],g-dp[i][0]-dp[mx2][0]+dp[mx2][1]+dp[i][2]);
}
}
}