「eJOI2022」最长不友好子序列 题解

算法思路

本题使用动态规划和贪心优化来解决最长不友好子序列问题。核心观察是：由于约束条件只涉及相邻和间隔一个位置的元素，因此只需要维护有限的历史状态。

关键观察

1. 约束条件分析

不友好序列要求任意距离 $\leq 2$ 的元素互不相同：

• $b_i \neq b_{i+1}$（相邻元素不同）
• $b_i \neq b_{i+2}$（间隔一个位置的元素不同）

2. 状态设计优化

对于当前位置 $i$，只需要考虑前面最近的 $K = 6$ 个不同值的位置，因为更早的位置不会影响当前的约束检查。

代码解析

核心数据结构

const int MAXN = 2e5 + 5, K = 6;
int n, a[MAXN], lst[MAXN], f[MAXN][K + 1];
set<int> st;  // 维护最近出现的位置
vector<int> col[MAXN];  // 记录每个位置的前驱状态

离散化处理

vector<int> v;
for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    v.push_back(a[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (int i = 1; i <= n; ++i) {
    a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
}

动态规划过程

for (int i = 1; i <= n; ++i) {
    if (lst[a[i]]) st.erase(lst[a[i]]);  // 移除相同值的旧位置
    
    int j = 0;
    // 遍历最近的K个不同值位置
    for (auto it = st.rbegin(); it != st.rend() && j <= K; it++) {
        int x = *it;
        
        for (int k = 0; k < col[x].size(); ++k) {
            if (a[col[x][k]] == a[i]) continue;  // 跳过相同值
            f[i][j] = max(f[i][j], f[x][k] + 1);
        }
        
        col[i].push_back(x);
        f[i][j] = max(f[i][j], 2);  // 至少可以形成长度为2的子序列
        ans = max(ans, f[i][j]);
        j++;
    }
    
    st.insert(lst[a[i]] = i);  // 更新当前位置
}

算法正确性

状态转移保证

• $f[i][j]$ 表示以位置 $i$ 结尾，使用前 $j$ 个最近不同值位置时的最长长度
• 通过检查 $a[col[x][k]] \neq a[i]$ 确保不违反距离约束
• 只考虑最近的 $K$ 个位置，因为更早的位置不会影响当前决策

贪心策略正确性

维护最近出现位置的集合确保：

• 总是考虑最相关的前驱状态
• 避免重复值的干扰
• 在有限状态空间中完成最优决策

复杂度分析

• 离散化：$O(n \log n)$
• 动态规划：每个位置处理最多 $K$ 个前驱，每个前驱最多 $K$ 个状态
• 总复杂度：$O(nK^2)$，其中 $K = 6$

关键技巧

1. 离散化：将大范围数值映射到小范围，方便处理
2. 有限状态：利用问题特性，只维护最近 $6$ 个不同值位置
3. 集合维护：使用 set 动态维护最近出现位置
4. 状态压缩：通过 $K$ 的常数限制，将指数复杂度降为线性