5.27华为OD机试真题 新系统 - Skill执行链完整性检测 (JavaPyCC++JsGo)
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 执行
执行链的完整性规则：
首元素限制：执行链不能以扩展类型（type=1）或高级类型（type=2）开头，必须以基础类型（type=0）开头
依赖传递：
- 扩展类型（type=1）的直接前驱必须是基础类型（type=0）
- 高级类型（type=2）的前驱和前前驱都必须是基础类型（type=0）
- 链式依赖：每两个相邻的基础类型之间最多允许存在一个扩展类型或高级类型
给定一个类型数组 type，找到最长的连续 Skill 子链，使得子链满足完整性规则。返回该子链的长度。
数据规模
- 0 ≤ type.length ≤ 2000
2026 华为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. 基础类型(type=0)可以独立成链，也可以接在任何有效链后面 2. 扩展类型(type=1)必须以前一个基础类型为直接前驱 3. 高级类型(type=2)必须以前两个都是基础类型为直接前驱
状态定义
定义三个动态规划变量： -dp0: 以基础类型结尾的最长有效链长度 -dp1: 以扩展类型结尾的最长有效链长度 -dp2: 以高级类型结尾的最长有效链长度
状态转移
若type[i]==0(基础类型):nd0=1#独立成链nd0=max(nd0,dp0+1,dp1+1,dp2+1)#接在前面的有效链后面若type[i]==1(扩展类型):nd1=dp0+1#必须以前一个基础类型为前驱若type[i]==2(高级类型):nd2=dp0+1#必须以前两个基础类型为前驱复杂度分析
- 时间复杂度: O(n)，只需遍历一次数组
- 空间复杂度: O(1)，只使用常数个变