大厂真题 / 华为

华为 2026-10-28 笔试真题 - AI岗

本场考试概述

考试时间：2026年10月28日

考试岗位：AI岗

难度评级：中等

收录范围：已披露的 15 道单选题、5 道多选题和 2 道编程题。选择题答案按已有材料整理，存在适用条件或措辞不严谨之处时单独说明，不将其包装为无条件结论。编程题缺失的范围不自行补造。

考点分析：

选择题：激活函数、Softmax 与交叉熵、线性代数、误差传播、类别不平衡、量化与 KV Cache、Agent、Pass@k、代码分词和 CNN 反向传播。
第一题：离散特征的 ID3 决策树，重点是信息增益、平局处理与递归终止（中等）。
第二题：带段尾通信代价的连续分段，重点是“恰好分成 K 段”的动态规划（中等）。

建议策略：

选择题先判断表述是否过于绝对，分清题目期望答案与工程实现的具体条件。
决策树先明确停止条件、特征平局规则以及未知取值的预测约定，再写递归。
流水线切分先写出每段完整代价；不能把“至多 K 段”直接替换成“恰好 K 段”。

选择题：已披露的 20 道

一、单选题

1. 卷积层输出通道数

在图像特征提取中，卷积层输出的特征图（Feature Map）通道数通常由什么决定？

A. 卷积核（Kernel）的数量
B. 输入图像的通道数
C. 卷积核的大小
D. 步长（Stride）

答案：A。 标准卷积中，一个输出卷积核对应一个输出通道。输入通道数影响卷积核的输入维度，核大小与步长主要影响空间尺寸。

2. 输出范围为 (0, 1) 的激活函数

以下哪个激活函数的输出范围是 $(0,1)$？

A. Sigmoid
B. Tanh
C. Leaky ReLU
D. ReLU

答案：A。 Sigmoid 为 $\sigma(x)=1/(1+e^{-x})$。Tanh 的值域是 $(-1,1)$，ReLU 的值域是 $[0,+\infty)$；采用正的非零负半轴斜率时，Leaky ReLU 的值域是实数集。

3. 线性变换矩阵的作用

在机器学习中，常通过线性变换 $z=Wx$ 将输入向量 $x$ 映射到新的特征空间。其中矩阵 $W$ 的作用通常是什么？

A. 计算行列式
B. 特征变换或特征投影
C. 删除数据
D. 计算矩阵秩

答案：B。 每个输出坐标是输入分量的线性组合，表达的是特征映射。降维映射可能损失信息，但不是选项 C 所说的直接删除数据。

4. ReAct 的名称

在 Agent 架构中，ReAct 是一个经典范式，其名称代表哪两个单词的结合？

A. Real 和 Action
B. Read 和 Act
C. Recall 和 Activation
D. Reasoning 和 Acting

答案：D。 ReAct 将推理和行动结合，并根据工具或环境反馈继续处理任务。

5. 训练困惑度下降、验证困惑度上升

训练一个用于对话生成的千亿参数语言模型时，训练数据包含大量互联网文本与对话记录。训练困惑度持续下降，但独立收集的真实用户交互验证集上的困惑度先下降后迅速上升，同时生成内容大量重复训练数据中的特定句式，并出现事实性错误。哪项分析与解决方案最准确？

A. 问题为过拟合，模型记忆了噪声与特定样本；应仅采用交叉验证重新划分数据集，确保验证集与训练集分布完全一致。
B. 问题为过拟合，且伴随训练数据中的偏差被放大；应综合使用权重衰减、Dropout、早停，并引入 RLHF 优化生成内容的泛化性与事实性。
C. 问题为领域偏移；应放弃正则化，在验证集上继续微调直至困惑度不再上升。
D. 问题为欠拟合；应增加模型参数量或延长训练时间。

材料答案：B。 给定现象更符合过拟合，正则化与早停是合理措施。仅重新划分数据不足以解决问题，在验证集上训练会破坏独立评估。需要注意：RLHF 不是处理预训练过拟合的必需步骤，也不能保证事实性；验证集分布差异可能同时存在，不能仅凭这段描述完全排除。

6. 和的绝对误差限

已知 $x_1=1.23$，绝对误差限为 $0.005$；$x_2=4.56$，绝对误差限也为 $0.005$。则 $x_1+x_2$ 的绝对误差限为多少？

A. 0.02
B. 0.005
C. 0.015
D. 0.01

答案：D。 最坏情况下两项误差同向叠加，由三角不等式，和的绝对误差限为 $0.005+0.005=0.01$。这里不是独立随机误差的方差相加问题。

7. 量化与推理优化

关于量化与推理优化的协同设计，以下说法最准确的是？

A. 算子融合时，反量化必须与矩阵乘法分离为独立 kernel，以确保数值精度并保持实现简洁；融合会导致代码复杂度和精度损失。
B. 激活量化（如 INT8）的主要收益是减少显存，计算加速依赖权重量化；单独激活量化必须反量化到 FP16 后计算，无法利用低精度乘加指令。
C. KV Cache 量化只能通过更大 batch 或更长序列间接提升吞吐，不能直接加速单序列生成；解码阶段计算密集、带宽充足，压缩 Cache 不影响延迟。
D. 权重量化（如 INT4）主要减少模型加载时间和显存；部分 GPU 支持 INT4 张量核心，但受累加精度与软件生态限制，实际部署中会反量化到 FP16/BF16 计算。

材料答案：D。 在常见的 weight-only 实现中，低位权重可以在计算 kernel 内反量化，降低存储和访存成本。A 的“必须分离”和 C 对解码瓶颈的概括不成立；B 将硬件、算子和数据类型组合的限制说成普遍规律，也不准确。D 同样不是所有 INT4 部署的统一实现：是否直接使用低精度指令、能否加速，取决于硬件、算子和工作负载。

8. Agent 任务分解

Agent 处理复杂任务时，关于任务分解策略，哪项正确？

A. 分解一旦完成，执行中不能根据反馈调整
B. 必须从后向前，先规划最终目标再规划子任务
C. 遵循自顶向下的原则，将复杂问题分解为可管理、可执行的子任务
D. 只能划分为原子操作，不能再进一步拆分

答案：C。 自顶向下是常见策略，执行反馈也可以触发重新规划；并非所有任务都只能采用一种分解顺序。

9. 减少工具调用错误

为了增强使用工具的大模型 Agent 的可靠性，以下哪个策略是无效的？

A. 调用后验证返回结果，异常时自动重试或使用备用方案
B. 提供详细工具描述，包括功能、参数格式和可能的错误情况
C. 调用前检查输入参数的类型、范围等有效性
D. 限制调用频率，避免短时间内多次调用同一工具

材料答案：D。 若“错误”指工具选择、参数或结果理解错误，限频不能直接修正这些问题，而 A、B、C 更有针对性。但“无效”表述过强：限频对于配额限制、服务过载引起的失败确实有效。

10. 线性变换后的方差

随机变量 $X$ 的标准差为 $3$，则 $Y=-2X+10$ 的方差是多少？

A. -6
B. 36
C. 6
D. 18

答案：B。 根据 $\operatorname{Var}(aX+b)=a^2\operatorname{Var}(X)$，结果为 $(-2)^2\cdot3^2=36$。平移不改变方差，负系数也不会产生负方差。

11. Softmax 与交叉熵

关于分类问题中 Softmax 与交叉熵损失的组合，下列说法错误的是：

A. Softmax + 交叉熵的组合在反向传播时会产生梯度消失问题
B. 交叉熵直接计算预测概率与真实 one-hot 标签的负对数似然
C. Softmax 将任意实数向量转换为概率分布，各分量位于 (0, 1)，和为 1
D. 对正确类别，预测概率越接近 1，交叉熵损失越接近 0

答案：A。 对 logits 的梯度可化简为 $p-y$，不会仅因“错误类别概率饱和”就失去有效学习信号。但这不保证深层网络的其他位置绝不出现梯度消失。C 默认类别数至少为二、输入有限，并按实数运算讨论；有限精度实现还需数值稳定处理。

12. 输出范围不是 0 到 1

下列哪个激活函数的输出范围不是 0 到 1？

A. Sigmoid
B. Softmax（用于多分类输出层）
C. ReLU
D. Hardsigmoid

答案：C。 ReLU 的正半轴没有上界。Hardsigmoid 的输出会截断到 $[0,1]$；其余两项在通常条件下输出概率或概率分量。

13. Pass@k 中 k 的含义

关于代码生成常用指标 Pass@k 中的“k”，下列说法正确的是：

A. 对同一题生成 n 个候选（n ≥ k），随机抽取 k 个，其中至少一个通过就算成功
B. 把 k 道题的平均正确率作为指标
C. 生成时把 top_k 设置为 k
D. 从 k 个模型中选最强的一个

答案：A。 它衡量 k 个候选中至少有一个通过测试的成功率。对一题生成 n 个候选，其中 c 个通过时，常用估计量为：

\[1-\frac{\binom{n-c}{k}}{\binom{n}{k}}.\]

当 $n-c<k$ 时，分子的组合数按零处理。候选次数 k 与解码参数 top_k 无关。

14. 输出范围为非负实数

以下哪个激活函数的输出范围是 $[0,+\infty)$？

A. Tanh
B. Sigmoid
C. ReLU
D. Leaky ReLU

答案：C。 $\operatorname{ReLU}(x)=\max(0,x)$，负数截断为零，正数原样保留。

15. 相同向量的余弦相似度

两个向量完全相同时，余弦相似度的值为？

A. 1
B. 0
C. -1
D. 0.5

答案：A，前提是向量非零。 相同非零向量的内积等于模长平方，因此归一化后的比值为 1。若都是零向量，标准余弦相似度没有定义，不能直接套用此结论。

二、多选题

16. 代码大模型的分词设计

在代码大模型的分词设计中，以下说法正确的是？

A. 删除所有空格，依赖换行符区分代码块
B. 保留括号，运算符为独立 Token
C. 保留缩进为独立 Token
D. 变量名使用 BPE 切分

材料答案：B、C、D。 代码分词需要保留语法相关信息，删除所有空格可能改变程序含义。BPE 是处理变量名的一种常见子词方法。不过，运算符、缩进是否恰好各占独立 Token 由分词器决定，B、C 应理解为设计策略，而不是所有代码模型都满足的硬性规律；D 也不是唯一选择。

17. 特征缩放的原因

在将数据结构化为矩阵时，进行特征缩放（Feature Scaling）的原因包括？

A. 提升数值稳定性
B. 加速梯度下降收敛
C. 防止量纲大的特征主导模型
D. 改变数据的原始分布形状

答案：A、B、C。 合理缩放有助于改善数值尺度、优化条件和距离度量。这里讨论常见的标准化、线性归一化，不把改变分布形状作为目标；非线性变换另当别论，树模型也不一定需要特征缩放。

18. 极度类别不平衡

在正类先验很小的极度类别不平衡场景中，哪些说法通常正确？

A. 只要 TPR 很高，Precision 一定很高
B. 即使模型很差，Accuracy 也可能很高，因此不宜作为核心指标
C. 先验很小且 FPR 不够低时，Precision 往往很低
D. 阈值调得更严格通常会降低 Recall，但可能提高 Precision
E. PR 曲线或 Precision-Recall AUC 往往比 ROC AUC 更敏感地反映正类检测质量

答案：B、C、D、E。 设正类先验为 $\pi$，预测正类的概率非零时有：

\[\operatorname{Precision}= \frac{\pi\cdot\operatorname{TPR}} {\pi\cdot\operatorname{TPR}+(1-\pi)\cdot\operatorname{FPR}}.\]

负类数量巨大时，即使 FPR 看起来不高，也可能带来很多假正例，因此 A 不成立。提高判正阈值使 Recall 不增，但 Precision 不保证严格单调上升；D 中“可能”很重要。PR 指标也依赖类别先验，跨数据集比较需注意分布差异。

19. Embedding 应用场景

Embedding 将信息映射为包含语义的稠密向量。下列属于常见应用场景的有：

A. 推荐系统中用户与物品的类别嵌入，用于相似度匹配
B. 语音识别中语音信号的离散特征嵌入
C. 自然语言处理中单词的向量表示，如 Word2Vec 的线性嵌入变体
D. 图像分类中类别标签的数值化映射

答案：A、B、C。 用户、物品、词和离散语音单元都可以映射为向量。仅将类别标签编码成整数不等于学习了语义嵌入，因此按 D 的通常含义不选；若进一步学习类别向量，则又属于不同的设置。嵌入也不必总是比原始表示维度低。

20. CNN 反向传播

关于反向传播在 CNN 中的应用，下列分析正确的有：

A. 批归一化在反向传播时只需学习缩放、偏移两个参数，无额外梯度计算
B. 网络越深，反向传播越容易出现梯度消失或梯度爆炸
C. 卷积层的反向传播等价于对梯度图做转置卷积
D. 最大池化反向传播时，只将梯度回传给前向中最大值的位置

材料答案：B、C、D。 BN 还需要向输入传播梯度，训练时涉及批统计量，A 错误。深层网络的梯度连乘可能放大或缩小，残差连接、初始化等可以缓解。C 严格说对应卷积对输入的梯度，不是整个反向传播过程，权重梯度仍需另外计算。D 默认最大值位置唯一，或前向已按实现规则记录并列最大值中的一个位置。

第 1 题：基于信息增益的决策树分类器

题目描述

实现一个基于信息增益的离散特征决策树分类器。每条训练数据由 m 个整数特征和一个整数标签组成：

feature_1 feature_2 ... feature_m label

对样本集合 $S$，设其中第 c 类所占比例为 $p_c$，信息熵定义为：

\[H(S)=-\sum_{c:p_c>0}p_c\log_2 p_c.\]

按特征 A 的不同取值分组，取值 v 对应的样本子集记作 $S_v$。信息增益为：

\[IG(S,A)=H(S)-\sum_v\frac{\lvert S_v\rvert}{\lvert S\rvert}H(S_v).\]

从根节点递归建树：在尚未使用的特征中选择信息增益最大的特征，按其取值建立分支，再对子集重复这一过程。增益相同时选择特征索引较小者。如果当前子集标签全部相同，或已经没有特征可用，就建立叶子，输出当前子集的多数类。

概念示意中，天气特征 Outlook 可作为根节点，Sunny 对应 No、Overcast 对应 Yes，Rain 再按风力分为 Weak → Yes、Strong → No。已有文字只保留了树形示意，未保留对应训练表，因此不补造这张表。实际输入全部使用整数，不需要转换天气字符串。

输入描述与约束

第一行整数 m：特征数，$1<m\le50$。
第二行整数 n：训练样本数，$1<n\le2000$。
接下来 n 行，每行 m + 1 个整数，前 m 个是特征，最后一个是标签。
接下来一行整数 k：测试样本数。
接下来 k 行，每行 m 个整数，表示待分类样本。

材料未给出 k、特征值和标签值的数值范围，不能自行假定为二分类或只包含 0、1。

规则边界：原题文字明确了特征增益平局规则，但未明确“多数类票数相同”与“测试特征出现未知取值”的处理。下方实现沿用配套题解的补充约定：多数类平票时取较小标签，未知取值时返回当前节点的多数类。这两条不是新增的原题披露条件。

输出描述

输出 k 行，每行一个整数标签，顺序与测试数据一致。

样例

输入

输出

解释：第一个特征已经可以区分标签；第二个特征在训练集上也能完全区分标签，但增益相同应优先选择第一个。测试数据即使在这两个特征上取值不同，也按第一个特征分类。

思路分析

第一步：把信息增益变成计数。 对当前 rows 统计标签频数 cnt，即可计算划分前熵 base。对一个候选特征 f，按 row[f] 分组，统计每组的标签频数，再加权求组内熵。用 base 减去加权熵，便得到该特征的信息增益。

第二步：只在当前路径未用过的特征中选择。 对同一个节点，base 不随候选特征改变，所以最大化信息增益等价于最小化条件熵。feats 按原始索引升序保存，选中 best_f 后，子树只接收去掉它的 rest。不是把该特征从整棵树中全局删除：不同分支仍可独立选择。

第三步：控制平局与停止条件。 浮点对数求和可能让数学上相同的增益出现微小差异。实现采用 EPS = 1e-9，只有 gain > best_gain + EPS 才替换，数值近似相等时保留较小索引。这是浮点比较约定，不是原题额外给出的阈值；极接近但不相等的真实增益也可能被视作平局。

不要因为最优增益为零就提前停止。某些标签依赖多个特征的组合，单独看任一特征都可能没有增益。题目只要求在标签纯净或特征耗尽时结束，所以即使零增益也继续消耗一个特征，递归仍会终止。

第四步：每个节点保存多数类。 节点表示为 (label, feature, children)，叶子的 feature 为 -1。预测时沿取值对应的分支下行；取值没有对应子节点时，按补充约定直接返回当前 label，而不是根节点的多数类。

正确性证明

对剩余特征数作归纳，证明建树实现满足题目及明确标注的补充约定。

若样本标签唯一，返回该标签；若没有剩余特征，返回计数最多的标签，平票取较小者。因此终止节点正确。
否则，代码对每个候选特征逐样本计数，按定义计算各组条件熵和信息增益。按升序扫描并使用上述容差比较，选出浮点实现规则下的最佳特征。各分支恰好包含该特征对应取值的全部样本，彼此不重叠且覆盖当前子集。
每个子问题少一个可用特征，由归纳假设，其子树也正确实现相同规则。因此当前节点及整棵树满足递归构造定义，且路径长度不超过 m。

预测过程保持“当前节点对应已匹配的全部路径条件”这一不变量。存在分支时继续匹配，抵达叶子后输出叶子标签；不存在分支时按约定返回当前多数类。因此预测也符合规定。这里证明的是按 ID3 规则构造，不是证明这棵树在所有决策树中具有最少节点或最高泛化精度。

题解代码

import sys
from collections import Counter
from math import log2

EPS = 1e-9


def entropy(counts, total):
    return -sum((c / total) * log2(c / total) for c in counts)


def info_gain(rows, feature, base):
    groups = {}
    for row in rows:
        value, label = row[feature], row[-1]
        if value not in groups:
            groups[value] = Counter()
        groups[value][label] += 1
    total = len(rows)
    conditional = 0.0
    for cnt in groups.values():
        size = sum(cnt.values())
        conditional += size / total * entropy(cnt.values(), size)
    return base - conditional


def build_tree(rows, feats):
    cnt = Counter(row[-1] for row in rows)
    label = min(cnt, key=lambda value: (-cnt[value], value))
    if len(cnt) == 1 or not feats:
        return (label, -1, None)

    base = entropy(cnt.values(), len(rows))
    best_f, best_gain = -1, float("-inf")
    for feature in feats:
        gain = info_gain(rows, feature, base)
        if gain > best_gain + EPS:
            best_f, best_gain = feature, gain

    parts = {}
    for row in rows:
        parts.setdefault(row[best_f], []).append(row)
    rest = [feature for feature in feats if feature != best_f]
    children = {}
    for value, subset in parts.items():
        children[value] = build_tree(subset, rest)
    return (label, best_f, children)


def predict(node, features):
    while node[1] != -1:
        child = node[2].get(features[node[1]])
        if child is None:
            return node[0]
        node = child
    return node[0]


def solve():
    input = sys.stdin.readline
    m = int(input())
    n = int(input())
    train = [list(map(int, input().split())) for _ in range(n)]
    root = build_tree(train, list(range(m)))
    k = int(input())
    for _ in range(k):
        features = list(map(int, input().split()))
        print(predict(root, features))


if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度：建树 $O(nm^2)$，预测 $O(km)$。一个节点对每个候选特征扫描该节点的样本；同一深度的样本集合不重叠，总数不超过 n，深度不超过 m。标签计数及分组使用字典，按均摊常数操作分析。

空间复杂度：$O(nm+m^2)$，含训练数据、树、递归保留的样本引用以及每层复制的候选特征列表；测试样本逐条读取。常见简写为 $O(nm)$，但当样本很少、很多特征为常量时，路径上的剩余特征列表仍可能累计占用 $O(m^2)$，这里将其单独计入。

第 2 题：最优流水线并行切分

题目描述

把包含 N 层的深度神经网络部署到 K 个 GPU 上，采用顺序流水线并行。第 i 层计算耗时为 T[i]，输出张量对应的通信耗时为 S[i]。

相邻层在同一个 GPU 上，不产生层间通信耗时。
第 i 层和第 i + 1 层在不同 GPU 上，则产生 S[i] 的通信耗时，计入前一阶段，即以第 i 层结尾的 GPU。
将全部层按原顺序切分为恰好 K 个非空连续子序列，每段分配给一个 GPU。
最后一个阶段后面没有下一层，不收取输出通信费用，即便输入提供了 S[N]。

每个 GPU 的总耗时为其层计算耗时之和，加上该阶段末尾需要支付的通信耗时。求所有合法切分中，“单个 GPU 最大总耗时”的最小值。

输入描述与约束

第一行：N 个空格分隔的整数，表示 T。
第二行：N 个空格分隔的整数，表示 S。
第三行：整数 K，表示 GPU 数量。

输入没有单独的 N，也没有方括号或逗号。已有材料未给出 N、K、T[i]、S[i] 的明确数值上限。按“耗时”语义使用非负值；合法切分要求 $1\le K\le N$。非法输入如何输出未披露，代码不自行约定返回 -1。由于上限未披露，下面给出与材料一致的 $O(KN^2)$ 解法，不宣称它能处理任意大规模数据。

输出描述

输出一个整数，表示最优切分的最大 GPU 总耗时。

样例 1

输入

10
0
1

输出

解释：只有一层、一个 GPU，不发生跨卡通信，答案就是该层计算耗时。

样例 2

输入

10 20 15 25 30
5 10 5 20 0
3

输出

解释：一种最优切分为第 1～3 层、第 4 层、第 5 层：

GPU1：计算耗时 $10+20+15$，通信耗时 $5$，总耗时 $50$。
GPU2：计算耗时 $25$，通信耗时 $20$，总耗时 $45$。
GPU3：计算耗时 $30$，无末尾通信，总耗时 $30$。

因此该方案的瓶颈为 50，动态规划会在全部合法切分中得到这一最小值。

思路分析

第一步：为什么普通分段贪心不适用？ 没有通信开销时，把非负序列多切一刀不会增大任一段的和。因此常见做法可以二分答案，再贪心检查能否用至多 K 段装下。

本题增加一个切口，会给左段新增一笔段尾通信。材料给出的反例是 T = [1, 1]、S = [100, 0]、K = 2：一段时耗时为 2，恰好两段时瓶颈却为 101。因此上限 2 对“至多两段”可行，对“恰好两段”不可行。失败的是这个贪心判定与段数替换，不是答案上限本身失去了可行性的单调性。

第二步：用前缀和表达一段的代价。 以下公式使用从 1 开始的层编号，令：

\[pre[0]=0,\qquad pre[i]=\sum_{t=1}^{i}T[t].\]

设上一段结束于 b，本段为第 b + 1 到 i 层，则：

\[cost(b,i)=pre[i]-pre[b]+comm(i), \qquad comm(i)=\begin{cases}S[i],&i<N,\\0,&i=N.\end{cases}\]

段内通信免费，只看末尾是否连接下一张 GPU。代码数组从零开始，因此公式中的 S[i] 对应 s[i - 1]。

第三步：把段数写进状态。 令 $f[j][i]$ 表示前 i 层恰好组成 j 段时，这些阶段最大总耗时的最小值。特别注意：若 $i<N$，当前前缀的最后一段也需要支付向第 i + 1 层发送的费用；只有到达整网末尾 N 才免通信。

初始状态为 $f[0][0]=0$，其他状态为正无穷。枚举最后一个切口 b：

\[f[j][i]=\min_{j-1\le b<i} \max\bigl(f[j-1][b],\ pre[i]-pre[b]+comm(i)\bigr).\]

下界 $b\ge j-1$ 保证前 j - 1 段至少各有一层。
上界 $b<i$ 保证最后一段非空。
内层 max 计算某一种切法的瓶颈；外层 min 选择最优切法。
最终答案是 $f[K][N]$，而不是在所有不超过 K 的段数中取最小值。

第四步：滚动数组。 第 j 行只依赖第 j - 1 行，用 prev 保存上一行、cur 保存当前行。每完成一行就令 prev = cur。不能直接原地覆盖同一行，否则可能误用本轮状态，破坏“恰好 j 段”的语义。

正确性证明

对阶段数 j 归纳。

初始情况：零层划为零段没有耗时，对应 $f[0][0]=0$；其余零段状态不可行，设为正无穷，正确。

归纳步骤：考虑前 i 层的任意合法 j 段切分，其最后一段必然是 b + 1 到 i，且 $j-1\le b<i$。前 b 层恰好分为 j - 1 段。由归纳假设，这部分的最小瓶颈是 $f[j-1][b]$；最后一段的成本只取决于 b、i，与前面具体如何切分无关。

对固定 b，将前缀替换为最优划分不会增大总瓶颈，故该切口下的最优值就是递推式中的 max。枚举范围覆盖所有合法最后切口，并且每个有限候选都能由一个合法前缀加上一个非空末段构成，因此取最小值既不会漏掉最优方案，也不会引入非法方案。

归纳得到所有状态正确，故 $f[K][N]$ 正是恰好 K 个阶段的最优瓶颈。滚动数组只删除后续不再使用的行，不改变递推结果。

题解代码

import sys


def min_max_cost(t, s, k):
    n = len(t)
    pre = [0] * (n + 1)
    for i, value in enumerate(t, 1):
        pre[i] = pre[i - 1] + value

    inf = float("inf")
    prev = [inf] * (n + 1)
    prev[0] = 0
    for j in range(1, k + 1):
        cur = [inf] * (n + 1)
        for i in range(j, n + 1):
            comm = s[i - 1] if i < n else 0
            best = inf
            for b in range(j - 1, i):
                if prev[b] == inf:
                    continue
                last = pre[i] - pre[b] + comm
                candidate = max(prev[b], last)
                if candidate < best:
                    best = candidate
            cur[i] = best
        prev = cur
    return prev[n]


def solve():
    input = sys.stdin.readline
    t = list(map(int, input().split()))
    s = list(map(int, input().split()))
    k = int(input())
    print(min_max_cost(t, s, k))


if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度：$O(KN^2)$。有 $O(KN)$ 个状态，每个枚举至多 N 个切口；前缀和使每段代价在常数时间内求出。

空间复杂度：$O(N)$。存储输入数组、前缀和及两行 DP，不保留所有阶段数对应的状态。有效代价始终是整数，正无穷只作为不可达标记。

小结

选择题：基础公式之外，更要注意隐含条件。RLHF 不保证事实性、限频并非总是无效、代码分词粒度依赖具体实现，卷积对输入的梯度也不等于完整反向传播。
信息增益决策树：按当前子集计数、按路径删除已用特征，保证平局处理和停止条件一致。零增益不代表必须停止；题面未披露的预测规则需要明确标注为补充约定。
流水线切分：通信费用属于左侧阶段，网络最后一层免末尾通信。“恰好 K 段”必须进入状态，不能借用无通信版本的贪心可行性判断。
实现习惯：两题均使用标准输入输出，样例与代码在同一题目区块中；先核对输入格式和规则，再考虑性能优化。

这篇文章有帮助吗？

| GitHub 留言