本文主要是介绍Codeforces Round #595 (Div. 3) F. Maximum Weight Subset(树形DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://codeforces.com/contest/1249/problem/F
题目大意：给一个树，求满足一个集合的点权和，使得集合内所有点之间距离大于k且点权和最大
题目思路：真的完全想不出来。。实在太牛B了。这个DP设的就非常牛B，dp[i][j]表示以i为根的子树，点集中的点距离i的距离最少为j的子集的最大点权和。
为啥这么设呢？因为本题的难点在于，如何保证在孩子与孩子之间能保证大于k的关系，如果这么设的话，想要别人给出到根多少距离的答案都能给出，就能方便运算
dp[i][0]很简单，加上自己的点权，然后所有孩子都选dp[y][k]，因为到孩子是k，到自己就是k+1符合条件了。
剩下的呢，就是枚举，首先枚举最近距离，然后枚举哪个点做那个提供最近距离的点，剩下的都得乖乖跟他混。
所以max(i-1,k-i)的意思就是，首先最近距离不能小于i，所以到孩子的距离是i-1,到自己就是i了，然后呢，就是不能跟选出来的天命之子忤逆，天选之子到自己的距离是i，那么其他的孩子选出来的就必须大于等于k+1-i，孩子到父亲距离有1，那么就是k-i
由于dp[i][j]的j表示的是至少，所以最后还要从后往前来一波max
这题是真的牛B。。
以下是代码：
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
const int MAXN = 200+5;
const int MOD = 1e9+7;
int n,k,x,y;
int dp[MAXN][MAXN];
int a[MAXN];
vector<int>v[MAXN];
void dfs(int u,int fa){int len=v[u].size();rep(i,0,len-1){int y=v[u][i];if(y==fa)continue;dfs(y,u);}dp[u][0]=a[u];rep(i,0,len-1){int y=v[u][i];if(y==fa)continue;dp[u][0]+=dp[y][k];}rep(i,1,n-1){rep(j,0,len-1){int temp=0;int y=v[u][j];if(y==fa)continue;temp+=dp[y][i-1];rep(t,0,len-1){int p=v[u][t];if(p==fa||p==y)continue;temp+=dp[p][max(i-1,k-i)];}dp[u][i]=max(dp[u][i],temp);}}per(i,n,0)dp[u][i]=max(dp[u][i],dp[u][i+1]);
}
int main(){while(cin>>n>>k){memset(dp,0,sizeof(dp));rep(i,1,n)v[i].clear(),cin>>a[i];rep(i,1,n-1){cin>>x>>y;v[x].push_back(y);v[y].push_back(x);}dfs(1,-1);cout<<dp[1][0]<<endl;}return 0;
}
这篇关于Codeforces Round #595 (Div. 3) F. Maximum Weight Subset(树形DP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
