首页 > 其他分享 >P2015 二叉苹果树 二叉树dp

P2015 二叉苹果树 二叉树dp

时间:2023-03-12 19:45:46浏览次数:52  
标签:ch val int P2015 son 二叉树 dp define

P2015 二叉苹果树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这道题之所以可以不用背包树形的原因是:它一个经典二叉树dp问题

令son[x][0]为x的左儿子,son[x][1]为x的右儿子

对于x节点,肯定是由左边和右边转移过来的,这就是二叉树dp的特点。

对于左边而不是左儿子,我们留L条边,右边R=i-m;

转移: if(L==0) dp[x][i]=max(dp[x][i],dp[son[x][1]][i-1]+val[x][son[1]]); //全取右边

     else if(R==0) dp[x][i]=max(dp[x][i],dp[son[x][0]][i-1]+val[x][son[0]]); //全取左边

   else dp[x][i]=max(dp[x][i],dp[son[x][0]][L-1]+val[x][son[0]]+dp[son[x][1]][R-1]+val[x][son[1]]);

最后的答案为dp[1][m]

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back   
#define popb pop_back  
#define fi first
#define se second
const int N=200;
//const int M=200;
//const int inf=0x3f3f3f3f;     
//const ll INF=0x3ffffffffffff;
int T,n,m;
vector<int> g[N],son[N];
int val[N][N],dp[N][N];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
void dfs(int x,int fa)
{
    for(auto v:g[x])
    {
        if(v==fa) continue;
        son[x].pb(v);
        dfs(v,x);
    }
    if(!son[x].size()) return;
    for(int j=1;j<=m;j++) // 第x个节点保存 j 个树枝 
    {
        for(int L=0;L<=j;L++) //取x左节点 L 个树枝
        {
            
            int R;
            if(L==0) dp[x][j]=max(dp[x][j],dp[son[x][1]][j-1]+val[x][son[x][1]]);    
            else if(L==j) dp[x][j]=max(dp[x][j],dp[son[x][0]][j-1]+val[x][son[x][0]]);
            else
            {
                int R=j-L;
                dp[x][j]=max(dp[x][j],dp[son[x][0]][L-1]+val[x][son[x][0]]+dp[son[x][1]][R-1]+val[x][son[x][1]]); 
            }
        } 
    }
}
int main()
{
//    freopen("","r",stdin);
//    freopen("","w",stdout);
    n=read(),m=read();
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read(),t=read();
        g[u].pb(v);
        g[v].pb(u);
        val[u][v]=val[v][u]=t;
    }
    dfs(1,0);
    printf("%d",dp[1][m]);
    return 0;
}

 

标签:ch,val,int,P2015,son,二叉树,dp,define
From: https://www.cnblogs.com/Willette/p/17208882.html

相关文章

  • P2015 二叉苹果树 背包树形dp入门
    P2015二叉苹果树-洛谷|计算机科学教育新生态(luogu.com.cn) 背包树形dp主要是用来处理可以取若干个子节点若干个情况,来实现dp转移到父节点我们令dp[x][y][i]为......
  • 基于LAMP搭建WordPress博客
    1、安装Apache。1)执行如下命令,安装Apache服务及其扩展包。yum-yinstallhttpdmod_sslmod_perlmod_auth_mysql2)执行如下命令,查看Apache是否安装成功。httpd-v3......
  • 2020 年百度之星·程序设计大赛 - 初赛一 Dec 二维DP,预处理
    problemDecAccepts:1284Submissions:4572TimeLimit:2000/1000MS(Java/Others)MemoryLimit:32768/32768K(Java/Others)ProblemDescription初始有a,ba,b......
  • 通过matlab对比规则LDPC和非规则LDPC的误码率
    1.算法描述       LDPC码是麻省理工学院RobertGallager于1963年在博士论文中提出的一种具有稀疏校验矩阵的分组纠错码。几乎适用于所有的信道,因此成为编码界近年......
  • Android 集合数据在Sharedpreferences中的增删改查
    Android集合数据在Sharedpreferences中的增删改查Sharedpreferences作为一个轻量化的Android本地存储方式相信很多人都为其不能存集合而烦恼所以呢,我封了两个简易的方法希......
  • 【CF995F Cowmpany Cowmpensation】(dp+容斥)
    原题链接题意一棵\(n\)个节点的树,给每个节点分配工资(\([1,D]\)),子节点不能超过父亲节点的工资,问有多少种分配方案。$1\len\le3000$,$1\leD\le10^9$思......
  • P1433 吃奶酪 标签: 动态规划,dp | 状态压缩
    详见:https://www.luogu.com.cn/problem/P1433就不写基础原理了,直接看注释吧点击打开非map版#include<iostream>#include<cstdio>#include<cmath>#include<alg......
  • CentOS 7 部署 HDP 3.3.1
    一、环境服务器名称配置IP地址备注hdp-161-1418核/16G内存/300GSSD硬盘10.32.161.141MGR/Agenthdp-161-1428核/16G内存/300GSSD硬盘10.32.161.142Age......
  • 2023,最新wordpress建站教程
    在我们购买了虚拟主机之后,我们要如何用wordpress去搭建一个满足自己需求的网站呢?这篇文章就来详细讲一讲,用wordpress搭建一个网站的具体过程。1.购买域名并完成解析选择......
  • 【洛谷】P3365 改造二叉树(LIS)
    原题链接题意给定一颗二叉树,每次操作可以修改一个点的权值为任意整数,求将原树变为二叉搜索树的最小操作次数。注意:本题中的二叉搜索树定义为:每个左边儿子的权值都严格小......