zcmimi's blog

arrow_back动态dp共2篇文章

avatar
zcmimi
2020-09-03 21:35:00

LG 4719 【模板】"动态 DP"&动态树分治

给定一棵n个点的树,点带点权。

m次操作,每次操作给定x,y,表示修改点x的权值为y

你需要在每次操作之后

avatar
zc
2020-10-27 20:44:01

查看原题

点击跳转

解法一

最小权覆盖集 = 全集 - 最大权独立集

动态dp

只要把强制取点,不取点可以分别把点的权值改为正无穷与负无穷

解法二

倍增/树链剖分+树形dp

每次修改的两个点a,b构成一条链

可以链上连接的子树与链中间的点的结果不受修改影响,只有a,b的转移受影响,需要单独处理

那么我们可以把子树的答案都预处理出来,链中间部分可以用倍增或树链剖分维护

这样只需要处理a,b

f(i,0/1)表示i选/不选,以i为根的子树的最小代价,g(i,0/1)表示整棵树除了以i为根的子树的最小代价,可以通过树形dp求出

F(i,j,0/1,0/1)表示i选/不选,i2^j级祖先选/不选,i子树到ii2^j级祖先子树的最小代价,可以倍增求出

1/1
Search
search