#P1563. 2023.05.24-暑期实习-第三题-网络升级改造
-
ID: 33
Tried: 30
Accepted: 14
Difficulty: 8
2023.05.24-暑期实习-第三题-网络升级改造
题面描述
在一个满二叉树结构的网络中,节点上标有年度维护成本的非负整数。给定节点的数量和其对应的成本值,要求通过撤销一些节点来最大化节省的维护成本,但不能同时撤销原本直接相邻的两个节点。需要根据输入的节点信息,输出能够节省的最大维护成本。
思路
这道题是洛谷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[u][0]
为以节点u
为根的子树中,撤销节点u
时所能获得的最大维护成本。 dp[u][1]
表示不撤销节点u
时所能获得的最大维护成本。
- 我们定义
-
状态转移:
- 对于一个节点
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
的维护成本。
- 对于一个节点
-
递归遍历:
- 使用深度优先搜索(DFS)来遍历每个节点,计算其状态并填充
dp
数组。
- 使用深度优先搜索(DFS)来遍历每个节点,计算其状态并填充
代码
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();
题目描述
这天小红在优化他以前做过的一个网络部署的项目,由于软件技术的提升,可以撤销部署网络中的某些节点,以简化网络并降低维护成本。但是,在撤销节点时,不能同时撤销原本直接相邻的两个节点。给定一个满二叉树结构的网络,每个节点上都标有一个数值,表示该节点的年度维护成本。现在要求撤销一些节点,使得可以节省最大的维护成本。
输入的网络以广度优先遍历的方式给出,每个节点都有一个非负整数值表示其年度维护成本。若某个节点不存在,则以0表示。每个数值的范围为 0 到 1000。
输入描述
输入第一行为一个正整数N,表示后面有N个数值。其中1≤N≤10000
输入第二行为N个非负整数,表示网络节点每年的维护成本,按照满二叉树的广度优先遍历顺序给出。0 表示不存在该关联节点,0 只会存在于叶子节点上。
输出描述
输出能够节省的最大维护成本。
示例1
输入
7
5 3 5 0 6 0 1
输出
12
解释:
能够节省的最大维护成本为5 +6 + 1 = 12。
示例2
输入
7
2 7 8 2 4 9 2
输出
19
解释:
能够节省的最大维护成本为 2 + 8 + 9 = 19.