cf与各算法比赛|Codeforces Round #595 (Div. 3) F. Maximum Weight Subset cf与各算法比赛|codeforces

http://codeforces.com/contest/1249/problem/F
（最近有点不在状态）
题意：
给你一棵树，里面有n(n<=200)个节点，每条边的距离为1，每个点都有一个权值，让你在树里面挑一些点，组成一个集合，集合中任何点之间的距离都必须大于k，问集合内所有点的权值之和最大是多少

现在只考虑一个点
假如选择了这个点，那么：
可以选择跟它距离大于k的子节点（因为树的原因，每个子树可选择的数量大于等于1）
（对于节点0，假如k=2，那么对于左子树可以选择点4或者5，对于右子树可以选6或者7）

文章图片

假如没有选择这个点，那么：
对于它的子节点，可以选也可以不选（对于上面那张图假如不选0节点的话，可以选1节点，但是也可以不选1节点而选择2或者3节点）

针对这种情况，设dp方程为：
dp[i][j]: 在以点i为根的树中选择点组成集合的时候，其选择的节点层数（相对点i的层数而言）的最小值大于等于j时，能选到的集合的最大权值和

那么此时对于一个点x，假如集合中包含这个点，那么
dp[x][0]+= num[x] (num[x]表示x的权值）
然后对于x的每一个子节点to，dp[x][[0]+=dp[to][k]
假如集合中不包含点x，此时情况就稍微复杂一点，假如此时我选择了其中以一个子节点to1为根的dp[to1][a]，那么由于树的特性，我就可以选择其他子节点ton中的dp[ton][k-a]
如图：当k=2的时候，假如不选择点1

文章图片

此时我可以选择dp[2][0] , 然后对于另外一个子树，则选择dp[6][2-1]=dp[6][1]

#include #define ll long long #define ull unsigned long long using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 205; int dp[maxn][maxn], num[maxn]; int Head[maxn], Nxt[maxn<<1], To[maxn<<1]; int n, k, tot; void add_edge(int fro, int to) { Nxt[++tot] = Head[fro]; Head[fro] = tot; To[tot] = to; } void tree_dp(int now, int f) { int *head = Head, *nxt = Nxt, *to = To, *a = num; dp[now][0] = num[now]; for (int i = Head[now]; i; i = Nxt[i]) { int &to = To[i]; if (to == f) continue; tree_dp(to, now); } for (int i = 0; i < n; i++) { //深度 if (i == 0) { //点取自己 for (int j = Head[now]; j; j = Nxt[j]) { int &to = To[j]; if (to == f) continue; dp[now][0] += dp[to][k]; } } else { for (int j = Head[now]; j; j = Nxt[j]) { //找到一个点 int &to = To[j]; if (to == f) continue; int sto = dp[to][i - 1]; for (int kk = Head[now]; kk; kk = Nxt[kk]) { //那个除点之外的所有子树 int &tto = To[kk]; if (tto == f || tto == to) continue; sto += dp[tto][max(i - 1, k - i)]; } dp[now][i] = max(dp[now][i], sto); } } } for (int i = n; i; i--) { dp[now][i - 1] = max(dp[now][i - 1], dp[now][i]); } } int main() { cin >> n >> k; for (int i = 1; i <= n; i++) scanf("%d", num + i); for (int i = 1; i < n; i++) { int fro, to; scanf("%d %d", &fro, &to); add_edge(fro, to); add_edge(to, fro); } tree_dp(1, -1); cout << dp[1][0] << endl; return 0; }

【cf与各算法比赛|Codeforces Round #595 (Div. 3) F. Maximum Weight Subset】