其实不用dp，用贪心就可以了，因为是满足贪心策略的……由于每一个结点都必须被网络覆盖，考虑边缘情况，即叶节点。每一个叶子结点也必须被网络覆盖，那么把叶子结点的父结点装上网络装置必定比只在叶子结点上装网络装置结果更优。所以就从叶子结点开始，即倒序遍历，对于每一个没有被网络覆盖的结点，此时它已经变成边缘结点，就把它的父节点和父节点的父节点都打上覆盖标记并统计答案。

#include<bits/stdc++.h>
using namespace std;
bool mp[10000],book[10000];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n=1;
	while(cin>>mp[n])n++;
	int ans=0;
	for(int i=n;i>=1;i--){
		if(mp[i]&&book[i]==0){
			int k=i>>1;
			book[k]=1;
			book[k<<1]=1;
			book[k<<1|1]=1;
			book[k>>1]=1;
			ans++;
		}
	}
	cout<<ans;
}

写到一半发现好像也没有什么建树的必要.

#include <iostream>
#include <sstream>

using namespace std;

const int MAXN = 9000;
int arr[MAXN], n;

int ans;

int dp(int root) {
    if(!arr[root]) return 2;
    int left = 2, right = 2;
    if(root * 2 + 1 < n) left  = dp(root * 2 + 1);
    if(root * 2 + 2 < n) right = dp(root * 2 + 2);
    if(left == 2 && right == 2) return 0;
    if(left == 0 || right == 0) {ans++; return 1;}
    if(left == 1 || right == 1) return 2;
    return -1;
}

int main() {
    string s;
    getline(cin, s);
    for(int i = 0; i <s.size(); i++) {
        if(s[i] == '1' || s[i] == '0') arr[n++] = s[i] - '0';
    }
    int ret = dp(0);
    if(ret == 0) ans++;
    cout << ans << endl;
    return 0;
}

题目描述

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

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

该题是$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 状态逐层累积，使得在最小化基站数的前提下，确保所有节点都能被覆盖。