树形DPTag:
BZOJ 4987 Tree
MayFlyyh | DP | 2018-09-18
从前有棵树。
找出K个点A1,A2,…,Ak。
使得$∑dis(A_i,A_i+1),(1<=i<=K-1)$最小。
第一行两个正整数n,k,表示数的顶点数和需要选出的点个数。
接下来n-l行每行3个非负整数x,y,z,表示从存在一条从x到y权值为z的边。
1<=k<=n。
l<x,y<=n
1<=z<=10^5
n <= 3000
好题是好题。。完全没看懂题意... [阅读全文]
BZOJ 4033 [HAOI2015]树上染色
MayFlyyh | DP | 2018-08-16
有一棵点数为N的树,树边有边权。给你一个在0~N之内的正整数K,你要在这棵树中选择K个点,将其染成黑色,并
将其他的N-K个点染成白色。将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。
问收益最大值是多少。
设dp[i][j]为以i为子树,染j个黑点对全局的贡献
$dp[i][j]=dp[i][j-t]+dp[e][t]+cost$
cost考虑i的儿... [阅读全文]
题解 LuoGu P2279 消防局的设立
LuoGu P2279 消防局的设立
题目描述
2020年,人类在火星上建立了一个庞大的基地群,总共有n个基地。起初为了节约材料,人类只修建了n-1条道路来连接这些基地,并且每两个基地都能够通过道路到达,所以所有的基地形成了一个巨大的树状结构。如果基地A到基地B至少要经过d条道路的话,我们称基地A到基地B的距离为d。
由于火星上非常干燥,经... [阅读全文]