题解

问题分析

这是一个贪心 + 状态压缩动态规划问题。我们需要找到最小的模特数量 $k$，使得在 $N$ 次表演中不会失败。

关键约束

1. 不能连续忽略两次：最多只能连续忽略一次
2. 回应条件：必须选择领带长度 ≤ $x$ 的模特，并将其长度调整为 $x$
3. 模特数量限制：$k$ 个模特，每个模特初始长度为 $1$

关键观察

1. 问题转化：实际上是在寻找最小的颜色集合（模特的不同长度状态），使得能够处理整个序列
2. 状态表示：由于 $A_i \leq 21$，可以使用状态压缩 DP
3. 预处理：需要快速找到某些模式在序列中的出现位置

算法思路

状态压缩 DP + 预处理：

状态定义

• f[mask]：当使用颜色集合 mask 时，能够处理到的最大位置
• mask 的二进制位表示哪些长度值被模特使用

预处理数组

1. f1[i][j]：从位置 $i$ 开始，下一个出现值 $j$ 的位置
2. f2[i][j]：更复杂的模式匹配信息，用于处理连续忽略的情况

DP 状态转移

对于每个状态 mask：

1. 检查能否通过交换操作扩展当前状态
2. 找到下一个需要处理的值
3. 更新能够到达的最大位置

核心代码逻辑

预处理

for(int i=n; i>=1; i--) {
    for(int j=1; j<=21; j++) {
        f1[i][j] = f1[i+1][j];
    }
    // 更新f2数组
    if(f1[i][a[i]] != INF) {
        for(int j=1; j<=21; j++) {
            f2[i][j] = f2[f1[i][a[i]]][j];
        }
    }
    f1[i][a[i]] = i;
}

状态转移

for(int i=1; i<(1<<len); i++) {
    if(__builtin_popcount(i) >= ans) continue;
    
    int Maxx = 0;
    // 计算当前状态能处理到的位置
    for(int j=2; j<=len; j++) {
        if(i & (1<<(j-1)) && (!(i & (1<<(j-2))))) {
            Maxx = max(Maxx, f[i^(1<<(j-1))^(1<<(j-2))]);
        }
    }
    
    // 尝试扩展状态
    int Minn = INF;
    for(int j=1; j<=len; j++) {
        if(!(i & (1<<(j-1)))) {
            if(f1[Maxx][j] == INF) continue;
            for(int k=1; k<=len; k++) {
                if(i & (1<<(k-1))) continue;
                Minn = min(Minn, f2[f1[Maxx][j]][k]);
            }
        }
    }
    
    f[i] = Minn;
    if(f[i] >= n) {
        ans = min(ans, __builtin_popcount(i));
    }
}

复杂度分析

• 预处理：$O(N \cdot M)$，其中 $M = 21$
• 状态转移：$O(2^M \cdot M^2)$
• 总复杂度：$O(N \cdot M + 2^M \cdot M^2)$，在 $M = 21$ 时可行

算法步骤

1. 读入 $N$ 和序列 $A$
2. 预处理 f1 和 f2 数组
3. 初始化 DP 数组
4. 遍历所有状态，进行状态转移
5. 找到使用颜色数量最少且能处理整个序列的状态
6. 输出答案

算法标签

• 状态压缩动态规划
• 贪心算法
• 预处理优化
• 位运算
• 序列处理