p2015 二叉苹果树 树形依赖形背包

传送门：树形依赖性背包

题意：

给一个二叉苹果树，每个树枝上都有w个苹果，现在我们要剪枝，问保留q个树枝，最多有多少个苹果

题解：

很明显这是有依赖性关系的树，我们要剪掉某根树枝，要观察他是否有子叶，如果有，那减掉这以根树枝连带的它的下放也要被剪掉，所以存在依赖性，所以现在我们在树数进行背包即可。动态转移方程：dp[i][j]=max(dp[i][j],dp[i][k],dp[x][j-k])
dp[i][j]代表以i为根节点，取j个，动态转移方程是以i为根节点取j个等价于以i为根节点取k个，以i的子节点取取j-k个，两种状态进行比较即可

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=205;
struct node
{
int v;
int w;
} temp;
int dp[maxn][maxn];
int vis[maxn];
vector<node>vec[maxn];
int n,q;
void dfs(int u)
{
for(int i=0; i<vec[u].size(); i++)
{
int v=vec[u][i].v;
dp[v][1]=vec[u][i].w;
dfs(v);
for(int j=q; j>=1; j--)
{
for(int k=0; k<=j; k++)
{
if((j!=k&&j!=1)||u==1)
{
dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);
}
}
}
}
}
int main()
{
scanf("%d %d",&n,&q);
for(int i=1; i<n; i++)
{
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
temp.v=v;
temp.w=w;
vec[u].push_back(temp);
}
dfs(1);
printf("%dn",dp[1][q]);
}

最后

以上就是默默烤鸡为你收集整理的p2015 二叉苹果树 树形依赖形背包的全部内容，希望文章能够帮你解决p2015 二叉苹果树 树形依赖形背包所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。