题面描述

在一个满二叉树结构的网络中，节点上标有年度维护成本的非负整数。给定节点的数量和其对应的成本值，要求通过撤销一些节点来最大化节省的维护成本，但不能同时撤销原本直接相邻的两个节点。需要根据输入的节点信息，输出能够节省的最大维护成本。

思路

这道题是洛谷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])$

思路解析

1. 状态定义：

   • 我们定义 dp[u][0] 为以节点 u 为根的子树中，撤销节点 u 时所能获得的最大维护成本。
   • dp[u][1] 表示不撤销节点 u 时所能获得的最大维护成本。

2. 状态转移：

   • 对于一个节点 u，我们需要考虑它的左子节点 left 和右子节点 right。
   • 不撤销节点 u：如果我们选择不撤销 u，那么 left 和 right 必须被撤销，因此： [ dp[u][1] = dp[left][0] + dp[right][0] ]
   • 撤销节点 u：如果我们选择撤销 u，那么 left 和 right 可以被撤销也可以不撤销。我们需要选择使得维护成本最大的方案： [ dp[u][0] = arr[u] + dp[left][0] + dp[right][0] ] 其中 ( arr[u] ) 是节点 u 的维护成本。

3. 递归遍历：

   • 使用深度优先搜索（DFS）来遍历每个节点，计算其状态并填充 dp 数组。

代码

CPP

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

// 存储每个节点的维护成本
vector<int> arr;
// dp数组，dp[u][0]表示撤销u的情况下的最大维护成本，dp[u][1]表示不撤销u的情况下的最大维护成本
vector<vector<int>> dp;

// 深度优先搜索函数，用于计算dp值
void dfs(int u) {
    int left = u * 2 + 1; // 左孩子节点
    int right = u * 2 + 2; // 右孩子节点
    // 如果是叶子节点
    if (left >= arr.size()) {
        dp[u][0] = 0; // 撤销叶子节点的维护成本为0
        dp[u][1] = arr[u]; // 不撤销叶子节点的维护成本为自身的成本
        return;
    }
    // 递归计算左子树和右子树的dp值
    dfs(left); // 先计算左子树
    dfs(right); // 再计算右子树
    // 如果不撤销u，则u的左、右孩子都必须被撤销
    dp[u][1] = dp[left][0] + dp[right][0];
    // 如果撤销u，则可以选择左、右孩子是否撤销，取最大值
    dp[u][0] = arr[u] + max(dp[left][0], dp[left][1]) + max(dp[right][0], dp[right][1]);
}

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)); // 初始化dp数组

    dfs(0); // 从根节点开始计算

    // 输出能够节省的最大维护成本
    cout << max(dp[0][0], dp[0][1]) << endl;

    return 0;
}

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]))

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
    }
}

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]))
}

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();