蓝桥杯：JAVA结点选择（树形动态规划）

野性酷女 2022-04-03 16:48 160阅读 0赞

private static int dp[][] = new int[10002][2];
    private static int tree[][] = new int[10002][300];
    
    //构建树
    public static void createTree(int parent,int child){
        int i = 0;
        while (tree[parent][i]!=0) {
            i++;
        }
        tree[parent][i] = child;
    
    
    }
    
    //遍历
    public static void dfs(int child, int parent){
        int child_1 = tree[child][0];
        for(int i = 0;child_1!=0;i++){
            child_1 = tree[child][i];
            dfs(child_1,child);
            System.out.println(child);
            dp[child][1] += dp[child_1][0];
            dp[child][0] += dp[child_1][1]>dp[child_1][0]?dp[child_1][1]:dp[child_1][0];
    
    
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int root = 0;
        for(int i = 0;i<n;i++){
            int x = scanner.nextInt();
            if(i==0){
                root = x;
            }
            dp[x][1] = x;
        }
        for(int i = 0;i<n-1;i++){
            int parent = scanner.nextInt();
            int child = scanner.nextInt();
            createTree(parent,child);
        }
        dfs(root,0);
        int max = dp[root][1]>dp[root][0]?dp[root][1]:dp[root][0];
        System.out.println(max);
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，160人围观）

还没有评论，来说两句吧...

相关阅读

相关【蓝桥杯-筑基篇】动态规划

然后，我们遍历输入数组，并对于每个元素，我们遍历所有先前的元素并检查它们是否小于当前元素。最后，我们输出 dp 中的最大值，它表示输入数组中最长上升子序列的长度。解题思路...

素颜马尾好姑娘i/ 2024年04月20日 07:50/ 0 赞/ 83 阅读

相关 [蓝桥杯 2020 省 AB1] 走方格——动态规划

题目描述在平面上有一些二维的点阵。这些点的编号就像二维数组的编号一样，从上到下依次为第 1 至第 n 行，从左到右依次为第 1 至第 m 列，每一个点可以用行号和列

Bertha 。/ 2023年09月26日 18:18/ 0 赞/ 136 阅读

相关动态规划从入门到精通-蓝桥杯

一、了解动态规划 1.简单来说动态规划是一种状态转移与递推 2.例题引入——最少硬币问题有多个不同面值的硬币(任意面值)；数量不限；

喜欢ヅ旅行/ 2023年09月24日 19:03/ 0 赞/ 46 阅读

相关蓝桥杯方格取数动态规划

> 题目描述 > 设有NN的方格图(N< =10),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。 > 某人从图的左上角的A 点(1,1)出发，可以向下

朴灿烈づ我的快乐病毒、/ 2023年08月17日 15:43/ 0 赞/ 141 阅读

相关【蓝桥杯】蓝桥杯入门训练+蓝桥杯基础训练

BEGIN-1 A+B问题资源限制时间限制：1.0s 内存限制：256.0MB 问题描述输入A、B，输出A+B。输入格式输入的第一行包括两个

野性酷女/ 2022年12月03日 01:59/ 0 赞/ 458 阅读

相关蓝桥杯K好数（动态规划）

1、背景：动态规划是在20世纪50年代由美国数学家贝尔曼为研究最优控制问题而提出的，英文叫dynamic programming。在计算机

古城微笑少年丶/ 2022年06月01日 10:47/ 0 赞/ 162 阅读

相关蓝桥杯结点选择（树形动态规划）

这道题就是一道树的最大独立集问题。先看一下题目要求：问题描述有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被

小咪咪/ 2022年05月31日 06:48/ 0 赞/ 175 阅读

相关蓝桥杯：JAVA结点选择（树形动态规划）

private static int dp[][] = new int[10002][2]; private static int tree[][] = new

野性酷女/ 2022年04月03日 16:48/ 0 赞/ 161 阅读

相关蓝桥杯算法训练传纸条（动态规划）

问题描述　　小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线

怼烎@/ 2022年03月16日 15:46/ 0 赞/ 180 阅读

相关蓝桥杯算法训练（四）结点选择（树形动态规划）C语言

结点选择（树形动态规划）C语言问题描述有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权

短命女/ 2022年03月09日 21:14/ 0 赞/ 181 阅读