ARTICLE · 1369321
2026华为OD机考真题|进化长廊展示(2026.1
2026华为OD机考真题|进化长廊展示(2026.1
2026.10.25 华为 OD 机考这道 200 分的《进化长廊展示》,表面是摆标本,其实考的是状压 DP。
n 最多 15。暴力枚举 15! 种排列根本跑不完,得按位置从左往右放。好在规则把状态卡得很死:相邻食性必须一草一肉;同类型标本隔开至少 minGap 位;珍稀标本只能蹲两端——1 件随便挑头尾,2 件就两头各占一个。
观赏值之和是固定的,怎么摆都一样。所以不用管总分,只盯一件事:让相邻加成最大。
放第 pos 个位置时,状态记成 (mask, last, t2, t3)——哪些标本用过、上一件是谁、前两件的类型。mask 用位掩码存,这就是状压的核心。
坑全在细节里:规则 1 比的是摆放位置差,不是输入数组的下标;加成是无向的,u,v 和 v,u 都得查到;没合法方案要返回 -1。
复杂度 O(S·n),S 是能走到的状态数。因为食性必须交替,实际状态远少于最坏情况,n=15 实测也就几十万级。
写完别急着过下一题,去 CodeSeeking 跑满那 20 组测试点再说。















































































