规划 - 题目列表

暴力
1. 题目核心分析
2. 第一步：数学推导 (01 分数规划)
3. 第二步：算法设计 (树上背包 DP)
1. 3.1 状态定义
2. 3.2 转移方程
4. 第三步：代码实现的 3 个关键细节 (易错点)
1. 🛑 细节 1：初始化为负无穷
2. 🛑 细节 2：循环的顺序 (背包的维度)
不优化的代码
1. 优化的代码1
2. 🛑 细节 3：循环的边界 (连通性的保证)
5. 优化的代码2
6. 学习总结

暴力

暴力: 显然01序列,先写 $O(2^n)$

1. 题目核心分析

目标：在一棵树上，拆除 $M$ 个点（即保留 $K = N-M$ 个点），要求剩下的点连通，且满足：

\text{最大化} \frac{\text{总产值}}{\text{总污染}} = \frac{\sum w_i}{\sum c_i}

这道题是两个经典模型的结合：

数学模型：01 分数规划（处理比值最大化）。
算法模型：树上背包 DP（处理树上连通块的最优选法）。

2. 第一步：数学推导 (01 分数规划)

直接求比值很难，我们换个思路：二分答案。

假设我们猜测最终的最大比值是 $x$ 。

如果存在一种选法，使得 $\frac{\sum w_i}{\sum c_i} \ge x$ ，那么答案可能比 $x$ 更大。

通过移项变形（这是分数规划的套路）：

\sum w_i \geqslant x \cdot \sum c_i

\sum w_i - \sum (x \cdot c_i) \geqslant 0

\sum (w_i - x \cdot c_i) \geqslant 0

结论：

二分一个 $x$ 后，我们只需要把每个工厂的权值重新定义为 $v_i = w_i - x \cdot c_i$ 。

问题就变成了 $P(x)$ ：能否在树上找到一个包含 $K$ ( $K = n - M$ )个节点的连通块，使得新的权值和 $\geqslant 0$ ？

这里显然具体二分性

对于一个 $x$ , 如果 $P(x)$ 成立, 则对于 $P(x-1)$ 一定也成立
- 思维模型: 想象节点 $i$ 是一个高度 $w_i$ 的柱子, $x$ 想象成水位的高度
- 也可以用数学证明,关系那个最大污染值的答案集合 $A$
  - A 如果在 x 成立,则一定在 $x-1$ 成立

3. 第二步：算法设计 (树上背包 DP)

现在问题简化为：树上选 $K$ 个连通点求最大权值。这是一个经典的树上分组背包问题（类似于 P2014 选课）。

这里我来详细的写一下,我是如何理解 树上选 $K$ 个连通点求最大权值 是如何进行的DP思路的

对于一个有根(root)的树, 最终的 最大权值的 $K$ 个连通点 形成的集合:

1. 包含root
 	1.  这个问题就变成了: 把 $K-1$ 名额分配 给孩子$v$的能得到最大值是什么(枚举)
2. 不包含root, 那么就是在root的子树上
 	1. 这个问题就变成了 $\max(dp[v][K])$ ,其中 $v$ 是root的孩子

显然,得益于树的递归结构,孩子的问题依然可以拆分

3.1 状态定义

$dp[u][j]$ ：在以 $u$ 为根的子树中，选出 $j$ 个点（必须包含 u 自己），所能得到的最大权值和。
- 这种点i,选或不选的,设DP的时候,通常设为一定选
  1. 方便思考
  2. 不选这个节点的情况,被其他问题包含了
为什么必须选 u？ 如果不选 $u$ ，它的子节点就没法和上面的节点连通了，连通性会断裂。

3.2 转移方程

我们在处理节点 $u$ 时，把它看作一个背包，它的每一个子节点 $v$ 都是一组物品。

$u$ 初始状态： $dp[u][1] = v_u$ (只选自己)，其余为 $-\infty$ 。
我们要决定给子树 $v$ 分配多少个名额（设为 $k$ ）。

dp[u][j] = \max(dp[u][j], \quad dp[u][j-k] + dp[v][k])

4. 第三步：代码实现的 3 个关键细节 (易错点)

这是你之前最容易卡住的地方，请仔细阅读：

🛑 细节 1：初始化为负无穷

因为 $v_i = w_i - x \cdot c_i$ 可能是负数，且我们要求必须填满 $j$ 个点。如果初始化为 0，程序可能会错误地认为“没选够点权值为0”比“选够了点但权值为负”更优，导致逻辑错误。

C++

for (int i = 1; i <= K; i++) dp[u][i] = -1e9; // 也就是 -INF
dp[u][1] = w[u] - x * c[u]; // 只有选1个点（自己）是合法的初始状态

🛑 细节 2：循环的顺序 (背包的维度)

这是一个分组背包。

第一层：枚举子节点 $v$ （物品组）。
第二层：枚举当前背包容量 $j$ （必须倒序！，防止重复选取）。
第三层：枚举分给子树 $v$ 的容量 $k$ 。

不优化的代码

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-05 23:31:22
 * Problem: P1642 规划
 * Algorithm: 01分数规划 + 树形DP (分组背包)
 * * 核心思想：
 * 1. 二分答案 x (假设最大比值为 x)
 * 2. 判定不等式 sum(w) / sum(c) >= x  =>  sum(w - x*c) >= 0
 * 3. 问题转化为：在树上选 K 个连通点，使得新权值 (w - x*c) 的和最大
 */

#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 2e2+5;
const double NINF  = -1e9; // 负无穷：因为权值可能是负数，初始化必须足够小

int n, m, K; // K: 最终需要保留的节点数量 (N - M)
int w[maxn]; // 产值
int c[maxn]; // 污染值
double dp[maxn][maxn]; // dp[u][j]: 以u为根的子树，选j个点(必须包含u)的最大权值
int sz[maxn]; // 子树大小

std::vector<int> g[maxn]; // 邻接表存图

// 预处理子树大小 (虽然N=100时可以不优化，但这是个好习惯)
void dfs_get_sz(int u, int fa) {
    sz[u] = 1;
    for(int v : g[u]) {
        if(v == fa) continue;
        dfs_get_sz(v, u);
        sz[u] += sz[v];
    }
}

// 读入数据并建图
void init() {
    std::cin >> n >> m;
    K = n - m; // 题目要求拆除M个，也就是保留 N-M 个
    
    for(int i = 1; i <= n; ++i) std::cin >> w[i];
    for(int i = 1; i <= n; ++i) std::cin >> c[i];
    
    for(int i = 2; i <= n; ++i) {
        int u, v;
        std::cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs_get_sz(1, 0); // 先算出每个子树有多大
}

/**
 * 核心 DP 函数
 * u: 当前节点
 * fa: 父节点 (防止往回走)
 * x: 当前二分检查的比值
 */
void dfs(int u, int fa, double x) {
    // 【关键点1】权值转换
    // 将求比值转化为求和：新的点权 = w[u] - x * c[u]
    // 状态初始化：只选 u 自己 1 个点的情况
    dp[u][1] = (double)w[u] - x * c[u];

    // 初始化其他状态为负无穷
    // 因为必须选 u 才能连通，如果凑不够 i 个点，该状态就是非法的
    for(int i = 2; i <= K; ++i) 
        dp[u][i] = NINF;

    // 遍历每一个子节点 (相当于分组背包中的“物品组”)
    for(int v : g[u]) {
        if(v == fa) continue;
        
        // 递归处理子树，先把子树的最优解算出来
        dfs(v, u, x);

        // 【关键点2】树上分组背包合并
        // j: 当前 u 子树准备选的总点数 (背包容量)
        // 必须倒序枚举！防止同一个子树被重复利用 (和 0/1 背包同理)
        for(int j = K; j >= 2; j--) {
            
            // k: 分给子树 v 的点数 (组内物品枚举)
            // k 的上限是 j-1，这是为了保证 u 自己必须占 1 个位置！
            // 如果 k = j，说明全部分给了子树，根节点 u 就没被选中，连通性就断了
            for(int k = 1; k <= j - 1; k++) {
                // 状态转移：尝试把子树 v 选 k 个的方案合并进来
                dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]);
            }
        }
    }
}

// 检查函数：判断是否存在一种选法，使得平均值 >= x
bool check(double x) {
    dfs(1, 0, x); // 以1为根进行DP
    
    // 只要树中任意一个位置，凑够了 K 个点，且权值和 >= 0
    // 说明实际比值可以达到 x (甚至更大)
    for(int i = 1; i <= n; ++i) {
        if(dp[i][K] >= 0) return true;
    }
    return false;
}

signed main() {
    // 加速 C++ 输入输出
    ios::sync_with_stdio(false); cin.tie(0);
    init();

    // 【关键点3】二分答案
    // 答案的范围：最小是 0，最大也就是 max(w_i) / min(c_i) <= 10000
    double l = 0, r = 10000;

    // 固定循环 100 次
    // 这是竞赛常用技巧：比 while(r - l > eps) 更快且不用担心精度死循环
    // 2^100 次方在这个范围内精度已经极高了
    for(int i = 0; i < 100; i++) {
        double mid = (l + r) / 2;
        if(check(mid)) 
            l = mid; // 可行，说明答案可能更大，尝试往右找
        else
            r = mid; // 不可行，说明猜大了，往左找
    }

    // 输出结果，保留一位小数
    std::cout << fixed << std::setprecision(1) << l << "\n";
    
    return 0;
}

优化的代码1

🛑 细节 3：循环的边界 (连通性的保证)

这是最难的一点。

cpp

// j 从大到小枚举
// 上限：不能超过 K，也没必要超过当前两棵树的大小之和
for (int j = min(K, sz[u] + sz[v]); j >= 2; j--) {
    
    // k 枚举分给子树 v 的点数
    // 上限 1：k <= sz[v] (子树只有这么大)
    // 上限 2：k <= j - 1 (必须至少留 1 个名额给 u 自己！)
    for (int k = 1; k <= min(sz[v], j - 1); k++) {
        dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]);
    }
}

PS: 可以不优化,这个题目 $N$ 最大100,可以过

$N = 100$ 。
我的代码1复杂度最坏是 $O(N^3)$ （其实是 $O(N \cdot K^2)$ ）。
计算量大约是 $100^3 = 1,000,000$ (一百万) 次运算。
现在的评测机通常一秒钟能跑 $10^8$ (一亿) 次运算。
为什么要 j - 1？ 如果 $k=j$ ，意味着把所有名额都给了子树 $v$ ，那根节点 $u$ 就没名额了。 $u$ 不选， $v$ 就断连了。

5. 优化的代码2

cpp

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

const int MAXN = 105;
const double INF = 1e9; 

int N, M, K; 
int w[MAXN], c[MAXN]; 
vector<int> adj[MAXN]; 
double dp[MAXN][MAXN]; 
int sz[MAXN]; 

void dfs(int u, int fa, double x) {
    sz[u] = 1;
    dp[u][1] = (double)w[u] - x * c[u];
    
    // 初始化：除了选1个点，其他都视为非法(-INF)
    for (int j = 2; j <= K; j++) dp[u][j] = -INF;

    for (int v : adj[u]) {
        if (v == fa) continue;
        dfs(v, u, x); // 1. 先把子树处理好

        // 2. 分组背包合并
        // j 倒序枚举，利用 sz 剪枝优化复杂度到 O(N^2)
        for (int j = min(K, sz[u] + sz[v]); j >= 2; j--) {
            // k 不能取到 j，必须给 u 留至少 1 个位置
            for (int k = 1; k <= min(sz[v], j - 1); k++) {
                dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);
            }
        }
        sz[u] += sz[v];
    }
}

bool check(double x) {
    dfs(1, 0, x);
    for (int i = 1; i <= N; i++) {
        if (dp[i][K] >= 0) return true; // 只要有一个连通块满足条件即可
    }
    return false;
}

int main() {
    scanf("%d %d", &N, &M);
    K = N - M; 

    for (int i = 1; i <= N; i++) scanf("%d", &w[i]);
    for (int i = 1; i <= N; i++) scanf("%d", &c[i]);

    for (int i = 1; i < N; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 二分答案
    double l = 0, r = 10000;
    for (int i = 0; i < 60; i++) { // 循环 60 次精度足够
        double mid = (l + r) / 2.0;
        if (check(mid)) l = mid;
        else r = mid;
    }

    printf("%.1lf\n", l);
    return 0;
}

6. 学习总结

看到“最大化比值” $\rightarrow$ 想到 01分数规划 (二分答案 + 转换权值)。
看到“树上选连通块” $\rightarrow$ 想到 树形 DP。
树形 DP 的核心 $\rightarrow$ 状态必须包含根节点，合并时注意倒序和给根节点留位。
复杂度优化 $\rightarrow$ 利用 sz[u] + sz[v] 控制循环上限，可以将树上背包的复杂度从 $O(N^3)$ 降低到 $O(N^2)$ 。

规划

目录

暴力