)
Skill执行链完整性检测2026 华为OD机试真题 5月27日华为OD上机新系统考试真题 100 分题型点击查看华为 OD 机试真题完整目录2026最新华为OD机试新系统卷 双机位C卷 真题题库目录全覆盖题库 逐点算法考点详解题目描述在 AI 助手的技能系统中执行链由多个 Skill 按顺序排列。每个 Skill 有一个类型标记type[i]0: 基础类型 Skill无依赖可以独立执行type[i]1: 扩展类型 Skill依赖前一个 Skill 执行type[i]2: 高级类型 Skill依赖前两个 Skill 执行执行链的完整性规则首元素限制执行链不能以扩展类型type1或高级类型type2开头必须以基础类型type0开头依赖传递扩展类型type1的直接前驱必须是基础类型type0高级类型type2的前驱和前前驱都必须是基础类型type0链式依赖每两个相邻的基础类型之间最多允许存在一个扩展类型或高级类型给定一个类型数组 type找到最长的连续 Skill 子链使得子链满足完整性规则。返回该子链的长度。数据规模0 ≤ type.length ≤ 20002026 华为OD机试真题 5月27日华为OD上机新系统考试真题 100 分题型点击查看华为 OD 机试真题完整目录2026最新华为OD机试新系统卷 双机位C卷 真题题库目录全覆盖题库 逐点算法考点详解输入描述类型数组 type输出描述该子链的长度示例1输入[0,0,0]输出3说明全为基础类型,满足规则(不违反任何约束)示例2输入[0,1,0,1]输出4说明0→1✓ (基础后接扩展)1→0✓(扩展后接基础)0→1✓(基础后接扩展)无违反规则,整个链有效示例3输入[2,0,0]输出2说明首元素高级类型违规从位置 1 开始 [0,0] 长度 2示例4输入[0,1,0,0,2]输出5说明0→1✓(基础后接扩展)1→0✓(扩展后接基础)0→0✓ (基础后接基础)0→0→2✓ (基础、基础后接高级)解题思路本题是一个动态规划问题核心在于维护以不同类型结尾的最长有效链长度。关键观察1. 基础类型(type0)可以独立成链也可以接在任何有效链后面 2. 扩展类型(type1)必须以前一个基础类型为直接前驱 3. 高级类型(type2)必须以前两个都是基础类型为直接前驱状态定义定义三个动态规划变量 -dp0: 以基础类型结尾的最长有效链长度 -dp1: 以扩展类型结尾的最长有效链长度 -dp2: 以高级类型结尾的最长有效链长度状态转移若type[i]0(基础类型):nd01#独立成链nd0max(nd0,dp01,dp11,dp21)#接在前面的有效链后面若type[i]1(扩展类型):nd1dp01#必须以前一个基础类型为前驱若type[i]2(高级类型):nd2dp01#必须以前两个基础类型为前驱复杂度分析时间复杂度: O(n)只需遍历一次数组空间复杂度: O(1)只使用常数个变
)
