1575 二叉苹果树

苹果树"/>

1575 二叉苹果树

1575 二叉苹果树

给定需要保留的树枝数量，求最多能留住多少苹果，是一个动态规划，并且是一个树形动态规划
个人感觉有点像贪心，不过没关系，因为动态规划的题第一眼都容易看成贪心
我们发现一个性质，那就是对于一根树枝，你选择了它，你也必须选择从这根枝条到根的所有枝条
设f[i][j]表示i个节点保留j根枝条所能获得的最大苹果树
f[x][p]=max(f[x][p]，f[x][p-j-1]+f[k][j]+e[i].v)
其中f[x][p-j+1]这个问题我想了很长时间，就是选择这个点，必须选择从这根枝条到根的所有枝条，f[k][j]表示子节点的枝条，e[i].v表示权值

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int SIZE=10005;
int n,q;
int x,y,z;
int f[SIZE][SIZE];
int head[SIZE],tot;
int b[SIZE];//计算枝条 
struct node{int next,to,v;
}e[SIZE];
void add(int x,int y,int z)
{e[++tot].to=y;e[tot].v=z;e[tot].next=head[x];head[x]=tot;
}
void dfs(int x,int father)
{for(int i=head[x];i;i=e[i].next){int k=e[i].to;//获取子节点 if(k==father) continue;dfs(k,x);b[x]+=b[k]+1;//计算枝条 for(int p=min(q,b[x]);p>=1;p--)//父节点的枝条 //从当前枝条开始倒序循环，min防止溢出{for(int j=min(p-1,b[k]);j>=0;j--)//子节点的枝条 f[x][p]=max(f[x][p],f[x][p-j-1]+f[k][j]+e[i].v);} }
}
int main()
{cin>>n>>q;for(int i=1;i<=n-1;i++){cin>>x>>y>>z;add(x,y,z);add(y,x,z);//邻接表存树 }dfs(1,0);cout<<f[1][q]<<endl;return 0;
}