寻找最富裕的小家庭 - 华为OD统一考试(C卷)
OD统一考试(C卷)
分值: 100分
题解: Java / Python / C++
题目描述
在一棵树中,每个节点代表一个家庭成员,节点的数字表示其个人的财富值,一个节点及其直接相连的子节点被定义为一个小家庭现给你一棵树,请计算出最富裕的小家庭的财富和。
输入描述
第一行为一个数N,表示成员总数,成员编号1-N,1<=N<=1000
第二行为N个空格分隔的数,表示编号1- N 的成员的财富值。 0 <= 财富值 <= 1000000
接下来 N-1 行,每行两个空格分隔的整数(N1,N2), 表示 N1 是 N2 的父节点。
输出描述
最富裕的小家庭的财富和
示例1
输入:
4
100 200 300 500
1 2
1 3
2 4
输出:
700
示例2
输入:
4
100 200 300 500
1 2
1 3
1 4
输出:
1100
题解
我们可以使用动态规划的思想来解决这个问题。
定义一个数组
f
,其中f[i]
表示与节点i
直接相连的子节点的财富和。通过遍历输入,将每个子节点的财富值累加到对应的父节点上,得到f
数组。最后,遍历整个树的节点,计算每个节点所在小家庭的财富和,取最大值即为最富裕的小家庭的财富和。
Java
import java.util.Scanner;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] vals = new int[n + 1];
for (int i = 1; i <= n; i++) {
vals[i] = scanner.nextInt();
}
// f[i] 表示与i直接相连的子节点财富和
i
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2024华为OD机试真题题解 文章被收录于专栏
华为OD机考(C卷、D卷)算法题库(绝对都是原题),帮助你上岸华为(已经不少小伙伴成功上岸)。提供Java、Python、C++ 三种语言的解法。每篇文章都有详细的解题步骤、代码注释详细及相关知识点的练习题。有问题,随时解答