Codeforces 1249D Maximum Weight Subset 题解
题意
给定一棵有$n$个结点的树和$k$,编号为$1\sim n$,结点$i$的权值为$a_i$ ($1\le n,k\le200,1\le a_i\le10^5$)。
现在请你选出一些节点,使得这些节点的权值和最大 并且 这些节点中任意两个节点的距离都$>k$。
并输出这个最大的权值。
题解
考虑树形DP。
以任意一个结点为根。设$dp(i,j)$表示在以结点$i$为根的子树内,选中结点中 离$i$最近的那个结点到$i$的距离大于等于$j$,权值最大的 选中结点的点集 的权值。
考虑以$u$为根的子树内,如何转移:
设$v$是$u$的任意一个儿子。
- $dp(u,0)=a_u+\sum dp(v,k)$。
- $dp(u,i)=\max\{dp(v,i-1)+\sum\limits_{w \text{is a son of} u,v\ne w} dp(w,\max(i-1,k-i)) \}$。
转移完后还要对$dp(u)$求一遍后缀最大值。
程序
1 | // #pragma GCC optimize(2) |