夢に僕らで帆を張って
来るべき日のために夜を超え

标签 树形DP 下的文章

November 11, 2019

洛谷P3177/HAOI2015 树上染色

题意有一棵点数为$N$的树,树边有边权。给你一个在$0 \sim N$之内的正整数$K$,你要在这棵树中选择$K$个点,将其染成黑色,并将其他 的$N-K$个点染成白色将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间的距离的和的受益。问受益最大值是多少数据范围:$0 \le k \le n \le 2000$题解因为计算答案时需要对整颗树考虑,而一条边的贡献为$$一侧的黑/白色点数...
November 11, 2019

洛谷P1270 “访问”美术馆

题意经过数月的精心准备,Peer Brelstet,一个出了名的盗画者,准备开始他的下一个行动。艺术馆的结构,每条走廊要么分叉为两条走廊,要么通向一个展览室。Peer知道每个展室里藏画的数量,并且他精确测量了通过每条走廊的时间。由于经验老到,他拿下一幅画需要5秒的时间。你的任务是编一个程序,计算在警察赶来之前,他最多能偷到多少幅画题解树上背包注意读入代码:#include<iostre...
November 11, 2019

洛谷P2014 选课

题意现在有N门功课,每门课有个学分,每门课有一门或没有直接先修课(若课程$a$是课程$b$的先修课即只有学完了课程$a$,才能学习课程$b$)。一个学生要从这些课程里选择$M$门课程学习,问他能获得的最大学分是多少?数据范围:$1 \le n,m \le 300$题解树上背包用$dp[u][i]$表示以$u$为根的子树中选择$j$门课的最大学分代码:#include<iostream&...
November 11, 2019

洛谷P1122 最大子树和

题意求树上联通块的最大权值和数据范围:$n \le 16000$题解树形$\text{dp}$用$dp[u]$表示以$u$为根的子树中的最大权值和代码:#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; co...
October 25, 2019

洛谷P2515/HAOI2010 软件安装

题意有$n$个软件可以安装,每个软件会占$w_i$的磁盘空间,价值为$v_i$ ,每个软件都有至多一个依赖。剩余磁盘空间为$m$,求安装软件的价值最大值数据范围:$0 \le n \le 100,0 \le m \le 500,0 \le v_i \le 1000$题解因为可能存在环,即必须全部安装才能有贡献,所以用$\mathrm{Tarjan}$缩点之后便是树形$\mathrm{dp}$...
October 18, 2019

洛谷P4099/HEOI2013 SAO

题意给出一个连成树的有向图,求拓扑序数量数据范围:$1 \le n \le 1000$题解树形$dp$,用$f[i][j]$表示以$i$为根的子树中,节点$i$的排名为$j$的方案数考虑转移,对于$u$为$v$的父节点,$x$在原序列中排名为$p_1$,新序列中排名为$p_3$;$y$在原序列中排名为$p_2$,新序列中排名为$p_4$,从$f[u][p_1]$与$f[v][p_2]$转移到...
September 26, 2019

洛谷P1273 有线电视网

题意:树上分组背包数据范围: $2 \le N \le 3000,1 \le M \le N-1$题解:算法:树形dp类似于01背包,考虑滚动数组优化。将每一个节点视为一个背包,其容量即为其子树大小。使用 $dp[u][i]$ 表示以 $u$ 为根节点的子树中,使用 $i$ 个子节点的最大值。可以得出状态转移方程:$$dp[u][i]=max(dp[u][i],dp[u][i-j]+dp[v...