题目描述

假设村落以二叉树的形状分布，我们需要选择在哪些村落建设基站。如果某个村落建设了基站，那么它和它相邻的村落（包括本节点、父节点和子节点）都会有信号覆盖。

计算出最少需要建设的基站数。

该题是$leetcode$原题:https://leetcode.cn/problems/binary-tree-cameras/solutions/422860/jian-kong-er-cha-shu-by-leetcode-solution/

思路：树上动态规划

1. 输入和树构建：输入是一个数组形式的完全二叉树，1 表示节点存在，0 表示节点不存在。代码通过递归构建二叉树。

2. 动态规划状态定义：定义 dp 状态表示在某个节点处的最小基站数需求，有三种状态：

   • dp_0: 该节点有基站，覆盖自己和左右子节点。
   • dp_1: 该节点没有基站，但被其子节点的基站覆盖。
   • dp_2: 该节点和其子节点都没有基站，但此节点会被其父节点的基站覆盖。

3. 递归和状态转移：在 dfs 函数中递归计算 dp 状态，根据左右子节点的不同 dp 状态更新当前节点的 dp 值。

   • 叶节点：如果是叶节点，则 dp_0 = 1（需要一个基站），dp_1 = inf（无法被子节点覆盖），dp_2 = 0（可被父节点覆盖）。
   • 非叶节点：根据左右子节点的 dp 值，使用不同的组合来最小化当前节点的 dp 值。 这三行代码实现了在当前节点放置基站或不放置基站的情况下，计算该节点的最小基站覆盖数量。这三种状态的计算基于左右子节点的 dp 值，具体解释如下：

1. node.dp_0 = min(left_0, left_1, left_2) + min(right_0, right_1, right_2) + 1

• 含义：dp_0 表示当前节点 node 自己放置一个基站的情况下，覆盖该节点和其子节点所需的最少基站数。
• 计算逻辑：
  • 在当前节点放置一个基站可以直接覆盖自己以及左右子节点。
  • 因此，左右子节点可以处于任意状态（dp_0, dp_1, dp_2），因为无论左右子节点是否放置基站，都能通过当前节点的基站信号覆盖到。
  • 为了最小化基站数量，我们取左右子节点的 dp 值中的最小值。
  • +1 表示在当前节点放置了一个基站。

2. node.dp_1 = min(left_0 + min(right_0, right_1), right_0 + min(left_0, left_1))

• 含义：dp_1 表示当前节点 node 不放置基站，但被其左右子节点的基站覆盖的情况下，所需的最少基站数。
• 计算逻辑：
  • 要实现这种覆盖，左右子节点中至少有一个必须放置基站来覆盖当前节点。
  • 这里有两种选择来最小化基站数量：
    • 左子节点放置基站（left_0），右子节点可被覆盖（min(right_0, right_1)）。
    • 右子节点放置基站（right_0），左子节点可被覆盖（min(left_0, left_1)）。
  • 这两种方案中取最小值，即为最少基站数量。

3. node.dp_2 = left_1 + right_1

• 含义：dp_2 表示当前节点 node 不放置基站，且依赖父节点放置基站覆盖自己的情况下，左右子节点的最小基站数。
• 计算逻辑：
  • 在这种情况下，当前节点必须通过父节点的基站信号覆盖自己，因此不能依赖左右子节点来覆盖自己。
  • 左右子节点也需要被覆盖到，因此它们各自必须满足 dp_1（即被它们的子节点覆盖）。
  • 左右子节点处于 dp_1 状态的总和即为 dp_2 的值。

4. 结果计算：在根节点处，返回 min(dp_0, dp_1) 即为满足覆盖条件的最小基站数。

python实现

arr = list(map(int, input().split()))  # 读取输入数组，表示二叉树的结构
n = len(arr)  # 节点数
inf = 10**9  # 设置一个很大的数作为无穷大，表示不可能的情况

class Node:
    def __init__(self):
        self.left = None  # 左子节点
        self.right = None  # 右子节点
        self.dp_0 = inf  # 该节点放置基站的最小基站数
        self.dp_1 = inf  # 该节点未放置基站，但被子节点覆盖的最小基站数
        self.dp_2 = inf  # 该节点未放置基站，但被父节点覆盖的最小基站数

root = Node()  # 初始化根节点

# 构建二叉树
def build_tree(node, i):
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] == 1:
        node.left = Node()
        build_tree(node.left, left)
    if right < n and arr[right] == 1:
        node.right = Node()
        build_tree(node.right, right)

build_tree(root, 0)  # 从根节点构建树

# 深度优先搜索计算dp状态
def dfs(node):
    if not node.left and not node.right:
        node.dp_0 = 1  # 叶节点放基站
        node.dp_1 = inf  # 叶节点无法通过子节点被覆盖
        node.dp_2 = 0  # 叶节点可以由父节点覆盖
        return

    # 左子节点的dp值
    if node.left:
        dfs(node.left)
        left_0 = node.left.dp_0
        left_1 = node.left.dp_1
        left_2 = node.left.dp_2
    else:
        left_0 = inf  # 左节点不存在时不可能放基站
        left_1 = 0  # 左节点不存在时默认被覆盖
        left_2 = inf  # 左节点不存在时不可能仅被父节点覆盖

    # 右子节点的dp值
    if node.right:
        dfs(node.right)
        right_0 = node.right.dp_0
        right_1 = node.right.dp_1
        right_2 = node.right.dp_2
    else:
        right_0 = inf
        right_1 = 0
        right_2 = inf

    # 当前节点的dp值
    node.dp_0 = min(left_0, left_1, left_2) + min(right_0, right_1, right_2) + 1
    node.dp_1 = min(left_0 + min(right_0, right_1), right_0 + min(left_0, left_1))
    node.dp_2 = left_1 + right_1

dfs(root)  # 从根节点开始执行DFS
print(min(root.dp_0, root.dp_1))  # 输出最小基站数，取根节点放基站或被子节点覆盖的较小值

cpp

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

// 定义二叉树节点结构
struct Node {
    Node* left;
    Node* right;
    int dp_0; // 当前节点放置基站的最小基站数
    int dp_1; // 当前节点未放置基站，但被子节点覆盖的最小基站数
    int dp_2; // 当前节点未放置基站，但被父节点覆盖的最小基站数

    Node() : left(nullptr), right(nullptr), dp_0(INF), dp_1(INF), dp_2(INF) {}
};

// 全局变量存储输入数组和节点数
vector<int> arr;
int n;

// 构建二叉树的递归函数
Node* build_tree(int i) {
    if (i >= n || arr[i] != 1)
        return nullptr;
    
    Node* node = new Node();
    node->left = build_tree(2 * i + 1);
    node->right = build_tree(2 * i + 2);
    return node;
}

// 深度优先搜索计算dp状态的递归函数
void dfs(Node* node) {
    if (!node->left && !node->right) {
        node->dp_0 = 1;    // 叶节点放基站
        node->dp_1 = INF;  // 叶节点无法通过子节点被覆盖
        node->dp_2 = 0;    // 叶节点可以由父节点覆盖
        return;
    }

    // 处理左子节点
    int left_0 = INF, left_1 = 0, left_2 = INF;
    if (node->left) {
        dfs(node->left);
        left_0 = node->left->dp_0;
        left_1 = node->left->dp_1;
        left_2 = node->left->dp_2;
    }

    // 处理右子节点
    int right_0 = INF, right_1 = 0, right_2 = INF;
    if (node->right) {
        dfs(node->right);
        right_0 = node->right->dp_0;
        right_1 = node->right->dp_1;
        right_2 = node->right->dp_2;
    }

    // 计算当前节点的dp_0
    node->dp_0 = min({left_0, left_1, left_2}) + min({right_0, right_1, right_2}) + 1;

    // 计算当前节点的dp_1
    node->dp_1 = min(left_0 + min(right_0, right_1),
                     right_0 + min(left_0, left_1));

    // 计算当前节点的dp_2
    node->dp_2 = left_1 + right_1;
}

int main(){
    // 读取输入数组
    string input_line;
    getline(cin, input_line);
    int num;
    stringstream ss(input_line);
    while (ss >> num){
        arr.push_back(num);
    }
    n = arr.size();

    // 构建二叉树
    Node* root = build_tree(0);
    if (!root){
        cout << 0;
        return 0;
    }

    // 执行深度优先搜索计算dp值
    dfs(root);

    // 输出最小基站数，取根节点放基站或被子节点覆盖的较小值
    cout << min(root->dp_0, root->dp_1);

    // 释放内存（可选）
    // 这里没有实现树的释放，为了简化代码

    return 0;
}

java

import java.util.*;
import java.io.*;

public class Main {
    static final int INF = (int)1e9; // 定义一个很大的数作为无穷大

    // 定义二叉树节点结构
    static class Node {
        Node left;  // 左子节点
        Node right; // 右子节点
        int dp0;    // 当前节点放置基站的最小基站数
        int dp1;    // 当前节点未放置基站，但被子节点覆盖的最小基站数
        int dp2;    // 当前节点未放置基站，但被父节点覆盖的最小基站数

        Node() {
            this.left = null;
            this.right = null;
            this.dp0 = INF;
            this.dp1 = INF;
            this.dp2 = INF;
        }
    }

    static List<Integer> arr = new ArrayList<>(); // 存储输入数组
    static int n; // 节点总数

    // 构建二叉树的递归函数
    static Node buildTree(int i) {
        if (i >= n || arr.get(i) != 1)
            return null;

        Node node = new Node();
        node.left = buildTree(2 * i + 1);   // 左子节点索引为2*i + 1
        node.right = buildTree(2 * i + 2);  // 右子节点索引为2*i + 2
        return node;
    }

    // 深度优先搜索计算dp状态的递归函数
    static void dfs(Node node) {
        if (node.left == null && node.right == null) {
            node.dp0 = 1;    // 叶节点放基站
            node.dp1 = INF;  // 叶节点无法通过子节点被覆盖
            node.dp2 = 0;    // 叶节点可以由父节点覆盖
            return;
        }

        // 处理左子节点
        int left0 = INF, left1 = 0, left2 = INF;
        if (node.left != null) {
            dfs(node.left);
            left0 = node.left.dp0;
            left1 = node.left.dp1;
            left2 = node.left.dp2;
        }

        // 处理右子节点
        int right0 = INF, right1 = 0, right2 = INF;
        if (node.right != null) {
            dfs(node.right);
            right0 = node.right.dp0;
            right1 = node.right.dp1;
            right2 = node.right.dp2;
        }

        // 计算当前节点的dp0
        node.dp0 = Math.min(Math.min(left0, left1), left2) + Math.min(Math.min(right0, right1), right2) + 1;

        // 计算当前节点的dp1
        node.dp1 = Math.min(left0 + Math.min(right0, right1),
                            right0 + Math.min(left0, left1));

        // 计算当前节点的dp2
        node.dp2 = left1 + right1;
    }

    public static void main(String[] args) throws IOException {
        // 读取输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputLine = br.readLine();
        String[] tokens = inputLine.trim().split("\\s+");
        for (String token : tokens) {
            arr.add(Integer.parseInt(token));
        }
        n = arr.size();

        // 构建二叉树
        Node root = buildTree(0);
        if (root == null) {
            System.out.println(0);
            return;
        }

        // 执行深度优先搜索计算dp值
        dfs(root);

        // 输出最小基站数，取根节点放基站或被子节点覆盖的较小值
        System.out.println(Math.min(root.dp0, root.dp1));
    }
}

核心逻辑总结

• dp_0 表示当前节点放基站。
• dp_1 表示当前节点不放基站，被子节点覆盖。
• dp_2 表示当前节点不放基站，期望被父节点覆盖。

通过 DFS 递归向上计算，每个节点的 dp 值基于子节点的 dp 状态逐层累积，使得在最小化基站数的前提下，确保所有节点都能被覆盖。

题目内容

假设村落二叉树形状分布，我们要选择在哪些村落建设基站。如果某个村落建设了基站，那么它和它相邻的村落(本节点、父节点，子节点)也会有信号覆盖。

计算出最少需要建设的基站数。

输入描述

使用完全二叉树的数组形式表示，从左到右，从上到下遍历，$1$表示节点存在，$0$表示节点不存在。

• $1<=$节点数范围$<=8191$
• $1$表示节点存在，$0$表示节点不存在。。

输出描述

基站个数

样例1

输入

1 1 1 1 0 1 1		

输出

2

说明

最少需要$2$个基站才能覆盖所有村落

样例2

输入

1 1 0 1 0 0 0

输出

1

说明

只需要$1$个基站就能覆盖所有村落