洛谷p2015二叉苹果树_洛谷二叉苹果树-程序员宅基地

技术标签: # 树形dp  

题目描述

有一棵苹果树,如果树枝有分叉,一定是分2叉(就是说没有只有1个儿子的结点)

这棵树共有N个结点(叶子点或者树枝分叉点),编号为1-N,树根编号一定是1。

我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树

2 5
\ /
3 4
\ /
1
现在这颗树枝条太多了,需要剪枝。但是一些树枝上长有苹果。

给定需要保留的树枝数量,求出最多能留住多少苹果。

输入格式

第1行2个数,N和Q(1<=Q<= N,1<N<=100)。

N表示树的结点数,Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。

每行3个整数,前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。

每根树枝上的苹果不超过30000个。

输出格式

一个数,最多能留住的苹果的数量。

输入输出样例
输入 #1

5 2
1 3 1
1 4 10
2 3 20
3 5 20

输出 #1

21

分析

这是一道经典的树形背包。
f [ a ] [ k ] f[a][k] f[a][k]表示以 a a a 为父节点的子树中,保留 k k k 根树枝所能保留的最多苹果树。
可以得到转移方程:
f [ a ] [ i ] = m a x ( f [ a ] [ j ] + f [ b ] [ i − j − 1 ] + c ) ( 0 ≤ j &lt; i ) f[a][i] = max(f[a][j] + f[b][i-j-1] + c)(0\leq j &lt; i) f[a][i]=max(f[a][j]+f[b][ij1]+c)(0j<i)
要注意对于每个节点 a a a ,我们要将 m m m 从大到小来更新 f [ a ] [ m ] f[a][m] f[a][m],以防止重复叠加。

下面是代码
//f[a][i] = max(f[a][j] + f[b][i-j-1]
#include <bits/stdc++.h>
#define N 105
using namespace std;
struct node{
	int a, b, c, n;
}d[N * 2];
int h[N], cnt, f[N][N], n, m;
void cr(int a, int b, int c){
	d[++cnt].a = a; d[cnt].b = b; d[cnt].c = c; d[cnt].n = h[a]; h[a] = cnt;
}
void dfs(int a, int p){
	int i, b, c, j, k;
	for(i = h[a]; i; i = d[i].n){
		b = d[i].b;
		c = d[i].c;
		if(b == p) continue;
		dfs(b, a);
		for(j = m; j >= 1; j--){
			for(k = 0; k < j; k++){
				f[a][j] = max(f[a][j], f[a][k] + f[b][j-k-1] + c);
			}
		}
	}
}
int main(){
	int i, j, a, b, c;
	scanf("%d%d", &n, &m);
	for(i = 1; i < n; i++){
		scanf("%d%d%d", &a, &b, &c);
		cr(a, b, c);
		cr(b, a, c);
	}
	dfs(1, -1);
	printf("%d", f[1][m]);
	return 0;
} 
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/iamhpp/article/details/99071360

智能推荐

vim ctags学习笔记-程序员宅基地

文章浏览阅读209次。vim ctags安装ctagstags文件生成tags文件导入tags文件ctags使用在vim命令行模式下在vim普通模式下针对多个项目的tags设置安装ctags解压:#tar xvf ctags-xx.tar.gz配置Makefle: ./configure编译&安装:#make & make installtags文件tags文件包含了用#define定义的宏、函数的定义和声明、变量、类、结构体、枚举、联合及其成员变量及函数tags文件没有包含函数使用信息,_vim ctags

CCCC-GPLT 考试前夕突击预习+复习记_ccccglp-程序员宅基地

文章浏览阅读292次。明天去c4,现在一个一个做来不及啦. 假装现在是考场上时间不够的情况,然后每个l3题写个暴力挣尽量多的分,从l3-005开始005 17:21开始想 17:27有解 18:05写完第一版,状态很差 改完bug 18:42 总结完成20:15 ????我在干什么??? 看来暴力也没有时间了emmm剩下的题明年做,现在飞速看一遍剩下的题. l2-013 红色警报 不用targan算法,..._ccccglp

python数据类型的性能分析_python自带类型的性能-程序员宅基地

文章浏览阅读137次。python数据类型的性能分析本文主要对Python两种内置数据类型list 和 dict上各种操作的大O数量级进行分析list与dict的比较list类型各种操作(interface)的实现方法有很多,如何选择具体哪种实现方法?总的方案就是,让最常用的操作性能最好,牺牲不太常用的操作80/20准则:80%的功能其使用率只有20%List基本操作的大O数量级..._python自带类型的性能

qt tablewidget 获取表头内容_verticalheaderitem-程序员宅基地

文章浏览阅读1.3w次,点赞6次,收藏22次。​​​ui->TableWidget->horizontalHeaderItem(0)->text();//获取表头第1行第1列的内容ui->TableWidget->horizontalHeaderItem(1)->text();//获取表头第1行第2列的内容ui->TableWidget->horizontalHeaderItem(..._verticalheaderitem

codeforces GYM101653 Q.Number Game dp-博弈论_gym 101653-程序员宅基地

文章浏览阅读379次。T(100)组数据,每组给出N(100)和1到N的一个排列,有两个玩家A和B,A先手操作. 每次操作一个人可以选择一个数拿走,要求是这个数左右相邻数都比它小,拿走后的位置为空. 最先拿走1的玩家赢,两者都是最优策略,问谁赢?还没有学习到博弈论的部分,但这道题实际上不是很难,略微思考可以做出来. 赢的条件是拿走1,注意到只有1所在的区间内数的信息有效,其他分割开的区间的信息只不过是数字个数..._gym 101653

java时间工具类(补充)_java 时间补点-程序员宅基地

文章浏览阅读801次。java时间工具类(补充)项目中,有些统计数据业务逻辑需要获取本月的数据,并且项目中所需要的数据是根据营业时间来判断的,所以不得不获取当月的第一天和当月的最后一天进行查询。/** * 获取当前月的第一天 **/ public static String getFirstDay() { SimpleDateFormat format = new Sim..._java 时间补点

随便推点

java之String, inputStream与Reader转换_inputstream 转reader-程序员宅基地

文章浏览阅读7.2k次。1、String –> InputStream InputStrem is = new ByteArrayInputStream(str.getBytes());或者ByteArrayInputStream stream= new ByteArrayInputStream(str.getBytes()); 2、InputStream–>String_inputstream 转reader

数据护航 安全立方—海泰方圆数据安全治理立体式框架_安全治理框架-程序员宅基地

文章浏览阅读1.2k次。数据库审计系统通过对数据库操作、访问用户,及外部应用用户的审计,来帮助用户事后生成合规报告、事故追根溯源,同时通过大数据搜索技术提供高效查询审计报告,定位事件原因,以便日后查询、分析、过滤,实现加强内外部数据库网络行为的监控与审计,提高数据资产安全。海泰方圆数据脱敏系统利用保留格式加密技术,能够在保留原有数据的有效信息特征的情况下,通过对部分数据进行遮蔽、替换、混淆等方法,对数据中敏感信息进行数据的变形,实现敏感隐私数据的可靠保护。相关技术包括身份认证、访问控制、数据分类分级、数据脱敏等。_安全治理框架

Linux 压缩和解压_linvx解压-程序员宅基地

文章浏览阅读105次。zip基本用法是:zip [参数] [打包后的文件名] [打包的目录路径]常用参数:-a 将文件转成ASCII模式-F 尝试修复损坏的压缩文件-h 显示帮助界面-m 将文件压缩之后,删除源文件-n 特定字符串 不压缩具有特定字尾字符串的文件-o 将压缩文件内的所有文件的最新变动时间设为压缩时候的时间-q 安静模式,在压缩的时候不显示指令的执行过程-r 将指定的目录下的所有子目录以及文件一起处理-S 包含系统文件和隐含文件(S是大写)例如:将指定目录/tmp压缩成test.zip文件_linvx解压

局域网搭建git服务器_集群中配置一个git bare仓库-程序员宅基地

文章浏览阅读7.9k次。安装git不详述服务器:远程仓库,局域网中一台充当服务器的机器本地:本地仓库,开发人员所用若干台机器1、首先,在服务器机器上新建一个文件夹,命名为pb或者之类可以识别的名称,主要作为仓库使用。通过Git命令行git init --bare新建一个仓库(必须用—bare参数,否则无法从本地push到服务器上)。之后把这个文件夹共享,共享给局域网中的用户。最终确定对方在网上邻居可以看到新建_集群中配置一个git bare仓库

Ubuntu1804 编译安装opencv的方法,亲测有效_ubuntu1804安装opencv440-程序员宅基地

文章浏览阅读513次。https://www.sohu.com/a/395356234_495675https://www.sohu.com/a/395356234_495675_ubuntu1804安装opencv440

解决Android 10 连接设备热点后无法创建Socket 问题_flutter android 连接局域网,设备间无法socket通信-程序员宅基地

文章浏览阅读2.2k次,点赞2次,收藏6次。解决Android 10 连接设备热点后无法创建Socket 问题在实际工作中,通常的配网方式为设备热点配网,这就需要手机连接上设备热点,App创建socket和设备建立通信。在工作中发现,将target 设置成29 时,无法创建socket。这里小编就提供一种解决方案NetworkSpecifier specifier = new WifiNetworkSpecifier.Builder() .setSsidPattern(new PatternMatcher(_flutter android 连接局域网,设备间无法socket通信

推荐文章

热门文章

相关标签