核心思路

本题要求找出最长的加油站序列，使得任意连续 $k$ 个加油站中不出现重复的网络编号。这是一个典型的带约束的最长子序列问题。

关键观察

1. 状态表示：由于 $k \leq 5$，可以用一个长度为 $k-1$ 的向量来表示最近选择的 $k-1$ 个加油站网络编号序列
2. 状态转移：对于每个新加油站，检查是否能加入到当前序列中而不违反约束

重要公式与算法

状态定义

设 $dp[vec]$ 表示以序列 $vec$（长度为 $k-1$）结尾的合法序列的最大长度，其中 $vec$ 记录了最近 $k-1$ 次加油的网络编号。

约束条件

对于新加油站 $a[i]$，可以加入到以 $vec$ 结尾的序列中当且仅当：

这保证了加入 $a[i]$ 后，新的连续 $k$ 个加油站（即 $vec$ 中的所有元素加上 $a[i]$）中没有重复网络。

状态转移

当 $a[i]$ 可以加入时：

其中 $new\_vec$ 是通过删除 $vec$ 的第一个元素并在末尾添加 $a[i]$ 得到的新序列。

优化策略

1. 空间优化：使用哈希表存储状态，避免存储所有可能的状态
2. 剪枝优化：定期清理不可能达到最优解的状态
   • 如果某个状态的值与当前最大值相差超过 $2k$，可以删除
   • 只保留与当前活跃网络相关的状态

算法复杂度

• 状态数：$O(n \cdot m^{k-1})$ 但实际远小于此上界
• 时间复杂度：$O(n \cdot \text{状态数})$，在约束下可行