题目

在一棵二叉苹果树上，保留k根枝条，使剩余的苹果数最大。

分析

树形dp，$f[i][j]$表示第i个节点保留j根枝条的最大苹果数
状态转移方程:$f[当前的点][j]=\max (f[当前的点][j-k-1]+f[孩子][k]+e[i].w)$
在O（n）的时间内可以求出答案

代码

#include <cstdio>
#include <cctype>
using namespace std;
struct tree{int y,w,next;}son[201];
int f[101][101],b[101],n,q,ls[101];
int in(){
int ans=0; char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans;
}
int min(int a,int b){return (a<b)?a:b;}
int max(int a,int b){return (a>b)?a:b;}
void dfs(int u,int last){
for (int i=ls[u];i;i=son[i].next)
if (son[i].y!=last){//没有走回去
dfs(son[i].y,u);//找孩子
b[u]+=b[son[i].y]+1;//b表示枝条的个数
for (int j=min(q,b[u]);j>=1;j--)//当前点的枝条
for (int k=min(b[son[i].y],j-1);k>=0;k--)//孩子的枝条
f[u][j]=max(f[u][j],f[u][j-k-1]+f[son[i].y][k]+son[i].w);
}
}
int main(){
n=in(); q=in();
for (int i=1;i<n;i++){
int x=in(),y=in(),w=in();
son[~-(i<<1)]=(tree){y,w,ls[x]}; ls[x]=~-(i<<1);
son[i<<1]=(tree){x,w,ls[y]}; ls[y]=i<<1;
}
dfs(1,0);
return !printf("%d",f[1][q]);
}

最后

以上就是长情大门为你收集整理的#树形dp#JZOJ 1661 洛谷 2015 二叉苹果树题目分析代码的全部内容，希望文章能够帮你解决#树形dp#JZOJ 1661 洛谷 2015 二叉苹果树题目分析代码所遇到的程序开发问题。

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