【备战秋招】每日一题:2023.05.24-华为OD-第三题-网络升级改造_华为od二叉树的广度优先遍历

为了更好的阅读体检，可以查看我的算法学习博客
在线评测链接:P1302

题目描述

这天塔子哥在优化他以前做过的一个网络部署的项目，由于软件技术的提升，可以撤销部署网络中的某些节点，以简化网络并降低维护成本。但是，在撤销节点时，不能同时撤销原本直接相邻的两个节点。给定一个满二叉树结构的网络，每个节点上都标有一个数值，表示该节点的年度维护成本。现在要求撤销一些节点，使得可以节省最大的维护成本。

输入的网络以广度优先遍历的方式给出，每个节点都有一个非负整数值表示其年度维护成本。若某个节点不存在，则以$0$表示。每个数值的范围为 $0$ 到 $1000$。

输入描述

输入第一行为一个正整数$N$，表示后面有$N$个数值。其中$1\le N\le 10000$

输入第二行为$N$个非负整数，表示网络节点每年的维护成本，按照满二叉树的广度优先遍历顺序给出。$0$ 表示不存在该关联节点，$0$ 只会存在于叶子节点上。

输出描述

输出能够节省的最大维护成本。

样例

输入

7
5 3 5 0 6 0 1
1
2

输出

12
1

解释：

能够节省的最大维护成本为$5$ + 6 + $1$ = $12$。

样例2

输入

7
2 7 8 2 4 9 2
1
2

输出

19
1

解释

能够节省的最大维护成本为 $2$ + $8$ + $9$ = $19$.

思路

这道题是洛谷P1352-没有上司的舞会一题的改版.具体做法是树形$DP$.

动态规划题目重点有两个:状态定义,状态转移.

状态定义

我们记$dp[u][0/1]$为当前以$u$为根节点的子树的最高维护成本,其中第二维度为0表示$u$根节点也被撤销,为1表示$u$根节点未被撤销.

状态转移

我们记$arr[u]$为$u$的权值,假设$left$是$u$的左孩子,$right$是$u$的右孩子,那么当我们选择不撤销$u$时,$left$和$right$必须被撤销.因此$dp[u][1]=dp[left][0]+dp[right][0]+arr[u]$.

现在我们考虑如果$u$被撤销时该如何选择.

我们发现$u$被撤销后,$left$和$right$都可以被撤销或者不被撤销.因此,按照贪心的思路,我们就判断$left$和$right$被撤销和不被撤销的两种情况哪一个维护成本高.具体就是求$max(dp[left][0],dp[left][1])$和$max(dp[right][0],dp[right][1])$.因此最后的转移方程为$dp[u][1]=max(dp[left][0],dp[left][1])+max(dp[right][0],dp[right][1])$

类似题目推荐

见知识点专栏-树上dp

代码

CPP

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> arr;
vector<vector<int>> dp;

void dfs(int u) {
    int left = u * 2 + 1;
    int right = u * 2 + 2;
    if (left >= arr.size()) {//如果是叶子节点,求到dp后直接return
        dp[u][0] = 0;
        dp[u][1] = arr[u];
        return;
    }
    dfs(left);//非叶子节点,就要先求到左子树的最大维护成本
    dfs(right);//和右子树的最大维护成本
    dp[u][0] = max(dp[left][0], dp[left][1]) + max(dp[right][0], dp[right][1]);//如果我们不撤销u
    dp[u][1] = dp[left][0] + dp[right][0] + arr[u];//如果我们撤销u
}

int main() {
    int n;
    cin >> n;
    arr.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    dp.resize(n, vector<int>(2));//处理输入

    dfs(0);

    cout << max(dp[0][0], dp[0][1]) << endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

python

n = int(input())
arr = [int(i) for i in input().split()]#处理输入
dp = [[0, 0] for i in range(len(arr))]

def dfs(u):
    left = u * 2 + 1
    right = u * 2 + 2
    if left >= n:#如果是叶子节点,求到dp后直接return
        dp[u][0] = 0
        dp[u][1] = arr[u]
        return
    dfs(left)#非叶子节点,就要先求到左子树的最大维护成本
    dfs(right)#和右子树的最大维护成本
    dp[u][0] = max(dp[left][0], dp[left][1]) + max(dp[right][0], dp[right][1])#如果我们不撤销u
    dp[u][1] = dp[left][0] + dp[right][0] + arr[u]#如果我们撤销u

dfs(0)
print(max(dp[0][0], dp[0][1]))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Java

import java.util.Scanner;

public class Main {
    static int n;
    static int[] arr;
    static int[][] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n];
        dp = new int[n][2];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }//处理输入

        dfs(0);

        System.out.println(Math.max(dp[0][0], dp[0][1]));
    }

    static void dfs(int u) {
        int left = u * 2 + 1;
        int right = u * 2 + 2;
        if (left >= n) {//如果是叶子节点,求到dp后直接return
            dp[u][0] = 0;
            dp[u][1] = arr[u];
            return;
        }
        dfs(left);//非叶子节点,就要先求到左子树的最大维护成本
        dfs(right);//和右子树的最大维护成本
        dp[u][0] = Math.max(dp[left][0], dp[left][1]) + Math.max(dp[right][0], dp[right][1]);//如果我们不撤销u
        dp[u][1] = dp[left][0] + dp[right][0] + arr[u];//如果我们撤销u
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

Go

package main

import "fmt"

func dfs(u int, arr []int, dp [][]int) {
	left := u*2 + 1
	right := u*2 + 2
	if left >= len(arr) {//如果是叶子节点,求到dp后直接return
		dp[u][0] = 0
		dp[u][1] = arr[u]
		return
	}
	dfs(left, arr, dp)//非叶子节点,就要先求到左子树的最大维护成本
	dfs(right, arr, dp)//和右子树的最大维护成本
	dp[u][0] = max(dp[left][0], dp[left][1]) + max(dp[right][0], dp[right][1])//如果我们不撤销u
	dp[u][1] = dp[left][0] + dp[right][0] + arr[u]//如果我们撤销u
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	var n int
	fmt.Scan(&n)

	arr := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&arr[i])
	}//处理输入

	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, 2)
	}

	dfs(0, arr, dp)

	fmt.Println(max(dp[0][0], dp[0][1]))
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

Js

function dfs(u, arr, dp) {
    const left = u * 2 + 1;
    const right = u * 2 + 2;
    if (left >= arr.length) {//如果是叶子节点,求到dp后直接return
        dp[u][0] = 0;
        dp[u][1] = arr[u];
        return;
    }
    dfs(left, arr, dp);//非叶子节点,就要先求到左子树的最大维护成本
    dfs(right, arr, dp);//和右子树的最大维护成本
    dp[u][0] = Math.max(dp[left][0], dp[left][1]) + Math.max(dp[right][0], dp[right][1]);//如果我们不撤销u
    dp[u][1] = dp[left][0] + dp[right][0] + arr[u];//如果我们撤销u
}

function main() {
    const readline = require('readline');//处理输入
    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout
    });

    let n;
    let arr;

    rl.on('line', (input) => {
        if (!n) {
            n = parseInt(input);
        } else {
            arr = input.split(' ').map(Number);
            rl.close();
        }
    });

    rl.on('close', () => {
        const dp = new Array(n).fill(null).map(() => new Array(2).fill(0));
        dfs(0, arr, dp);
        console.log(Math.max(dp[0][0], dp[0][1]));
    });
}

main();

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

题目内容均收集自互联网，如如若此项内容侵犯了原著者的合法权益，可联系我: (CSDN网站注册用户名: 塔子哥学算法) 进行删除。