http://acm.timus.ru/problem.aspx?space=1num=1018Binary Apple Tree

2024-01-10 07:18

本文主要是介绍http://acm.timus.ru/problem.aspx?space=1num=1018Binary Apple Tree,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意:给你一棵树,树上有很多苹果,现在要求你砍去一些树枝,问你砍去树枝后最多可以保留多少苹果,树形dp入门题

dp[i][j]表示以i为根节点保留j个树枝最多可以保留的苹果数。可得动态转移方程dp[i][j]=max(dp[i][j],dp[la][i]+dp[ra][j-i+1]);

AC代码:

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef struct node{
int lc;
int rc;
int s;
}Node;
Node tree[205];
int dp[105][105],apple[105][105];
bool visit[105];
int n;
void init()
{
memset(dp,-1,sizeof(dp));
memset(tree,0,sizeof(tree));
memset(apple,-1,sizeof(apple));
}
void Built_tree(int root){
visit[root]=true;
for(int i=1;i<=n;++i)
if(!visit[i]&&apple[root][i]!=-1){
if(tree[root].lc==0)  tree[root].lc=i;
else  tree[root].rc=i;
tree[i].s=apple[root][i];
Built_tree(i);
}
}
int Tree_dp(int p,int k)
{
if(dp[p][k]!=-1) return dp[p][k];
if(p==0||k==0) return  0;
dp[p][k]=0;
for(int i=0;i<=k-1;++i)
{
int l=Tree_dp(tree[p].lc,i);
int r=Tree_dp(tree[p].rc,k-1-i);
dp[p][k]=max(dp[p][k],l+r);
}
dp[p][k]+=tree[p].s;
return dp[p][k];
}
int main()
{
int m;
cin>>n>>m;
init();
for(int i=0;i!=n-1;++i)
{
int a,b,c;
cin>>a>>b>>c;
apple[a][b]=apple[b][a]=c;
}
Built_tree(1);
cout<<Tree_dp(1,m+1)<<endl;
return 0;
}


 

这篇关于http://acm.timus.ru/problem.aspx?space=1num=1018Binary Apple Tree的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/589994

相关文章

如何使用Docker部署FTP和Nginx并通过HTTP访问FTP里的文件

《如何使用Docker部署FTP和Nginx并通过HTTP访问FTP里的文件》本文介绍了如何使用Docker部署FTP服务器和Nginx,并通过HTTP访问FTP中的文件,通过将FTP数据目录挂载到N... 目录docker部署FTP和Nginx并通过HTTP访问FTP里的文件1. 部署 FTP 服务器 (

Qt实现发送HTTP请求的示例详解

《Qt实现发送HTTP请求的示例详解》这篇文章主要为大家详细介绍了如何通过Qt实现发送HTTP请求,文中的示例代码讲解详细,具有一定的借鉴价值,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1、添加network模块2、包含改头文件3、创建网络访问管理器4、创建接口5、创建网络请求对象6、创建一个回复对

springMVC返回Http响应的实现

《springMVC返回Http响应的实现》本文主要介绍了在SpringBoot中使用@Controller、@ResponseBody和@RestController注解进行HTTP响应返回的方法,... 目录一、返回页面二、@Controller和@ResponseBody与RestController

详解Java如何向http/https接口发出请求

《详解Java如何向http/https接口发出请求》这篇文章主要为大家详细介绍了Java如何实现向http/https接口发出请求,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 用Java发送web请求所用到的包都在java.net下,在具体使用时可以用如下代码,你可以把它封装成一

Node.js 中 http 模块的深度剖析与实战应用小结

《Node.js中http模块的深度剖析与实战应用小结》本文详细介绍了Node.js中的http模块,从创建HTTP服务器、处理请求与响应,到获取请求参数,每个环节都通过代码示例进行解析,旨在帮... 目录Node.js 中 http 模块的深度剖析与实战应用一、引言二、创建 HTTP 服务器:基石搭建(一

Python如何实现 HTTP echo 服务器

《Python如何实现HTTPecho服务器》本文介绍了如何使用Python实现一个简单的HTTPecho服务器,该服务器支持GET和POST请求,并返回JSON格式的响应,GET请求返回请求路... 一个用来做测试的简单的 HTTP echo 服务器。from http.server import HT

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

BUUCTF靶场[web][极客大挑战 2019]Http、[HCTF 2018]admin

目录   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 [web][HCTF 2018]admin 考点:弱密码字典爆破 四种方法:   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 访问环境 老规矩,我们先查看源代码