洛谷P3694题解：邦邦的大合唱站队问题（动态规划入门）

本文将详细讲解如何使用状态压缩动态规划解决洛谷P3694邦邦的大合唱站队问题，包含完整代码注释和逐步解析，适合算法新手学习。

一、问题理解

有N个偶像排成一列，每个偶像属于M个团队之一。现在要求相同团队的偶像必须站在一起（连续排列），问最少需要让多少人出列（出列后其他人向前移动填补空缺）才能满足条件。

‌输入格式‌：

• 第一行两个整数N, M (1≤N≤10⁵, 1≤M≤20)

• 第二行N个整数，表示每个偶像所属的团队编号

‌输出格式‌：一个整数，表示最少出列人数

二、核心思路

动态规划

由于M最大为20（团队数量少），而N最大为10⁵（总人数多），我们可以考虑使用‌状态压缩DP‌来解决这个问题：

1. ‌状态表示‌：dp[mask]表示已经排好了mask中为1的团队（从左到右连续排列）所需的最小出列人数

2. ‌状态转移‌：对于每个状态mask，尝试添加一个新的团队到已排序列的末尾

3. ‌代价计算‌：新添加的团队占据[len+1, len+cnt[i]]的区间，该区间内不属于该团队的人都需要出列

前缀和优化

为了快速计算任意区间中特定团队的人数，我们使用‌前缀和数组‌：

• sum[i][j]：前j个位置中属于团队i的人数

这样可以用O(1)时间计算区间[L,R]中团队i的人数：sum[i][R] - sum[i][L-1]

三、完整代码

#include <bits/stdC++.h>
using namespace std;

const int MAXN = 1e5+5;   // 最大人数
const int MAXM = 20;      // 最大团队数
const int INF = 0x3f3f3f3f; // 无穷大常量

int n, m;
int a[MAXN];            // 存储每个人所属的团队
int cnt[MAXM+2];        // 每个团队的人数统计
int sum[MAXM+2][MAXN];  // 前缀和数组，sum[i][j]表示前j个元素中i团队的人数
int dp[1<<MAXM];        // 状态压缩DP数组，大小2^MAXM

// 预处理前缀和数组
void preprocess() {
    for(int i=1; i<=m; i++) {
        for(int j=1; j<=n; j++) {
            // 计算第i个团队在前j个人中的数量
            sum[i][j] = sum[i][j-1] + (a[j]==i);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    // 输入数据
    cin >> n >> m;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        cnt[a[i]]++;  // 统计各个团队的人数
    }
    
    // 处理m=1的特殊情况（只有一个团队不需要调整）
    if(m == 1) {
        cout << 0 << endl;
        return 0;
    }
    
    // 预处理前缀和数组
    preprocess();
    
    // 初始化DP数组为无穷大
    memset(dp, INF, sizeof(dp));
    dp[0] = 0;  // 初始状态：没有团队被排列，出列人数为0
    
    // 遍历所有状态
    for(int mask=0; mask<(1<<m); mask++) {
        // 跳过无效状态
        if(dp[mask] == INF) continue;
        
        // 计算当前已排列团队的总人数
        int len = 0;
        for(int i=0; i<m; i++) {
            if(mask & (1<<i)) 
                len += cnt[i+1];  // i+1是因为团队编号从1开始
        }
        
        // 尝试添加新的团队
        for(int i=0; i<m; i++) {
            // 如果该团队尚未排列
            if(!(mask & (1<<i))) {
                // 新团队占据的区间：[len+1, len+cnt[i+1]]
                int l = len + 1;
                int r = len + cnt[i+1];
                
                // 处理可能的空区间情况
                if(l > r) continue;
                
                // 计算代价：区间长度 - 该区间内目标团队的人数
                // 即：该区间内不属于目标团队的人数（需要出列）
                int cost = (r-l+1) - (sum[i+1][r] - sum[i+1][l-1]);
                
                // 更新状态
                if(dp[mask] + cost < dp[mask | (1<<i)]) {
                    dp[mask | (1<<i)] = dp[mask] + cost;
                }
            }
        }
    }
    
    // 输出结果：所有团队都排列完成所需的最小出列人数
    cout << dp[(1<<m)-1] << endl;
    return 0;
}

四、代码解析

1. 状态压缩DP核心逻辑

for(int mask=0; mask<(1<<m); mask++) {    // 计算当前已排列团队的总人数len
    for(int i=0; i<m; i++) {        if(!(mask & (1<<i))) {            // 计算新团队占据的区间[l, r]
            int cost = (r-l+1) - (sum[i+1][r] - sum[i+1][l-1]);
            dp[mask | (1<<i)] = min(dp[mask | (1<<i)], dp[mask] + cost);
        }
    }
}

• mask表示当前已排列的团队集合

• len是已排列团队的总人数

• 新团队i占据区间[len+1, len+cnt[i+1]]

• cost是该区间内不属于团队i的人数

2. 前缀和数组的使用

int cost = (r-l+1) - (sum[i+1][r] - sum[i+1][l-1]);

• (r-l+1)：区间总长度

• sum[i+1][r] - sum[i+1][l-1]：区间内团队i+1的实际人数

• 差值即需要出列的人数（不属于该团队的人）

五、总结

本题展示了状态压缩DP在解决组合排列问题中的强大能力，特别是当元素数量较少（M≤20）但整体规模较大（N≤10⁵）时特别有效。关键思想是：

1. 使用二进制表示团队排列状态

2. 通过前缀和优化区间查询

3. 定义清晰的状态转移方程

这种技术还可扩展到其他排列组合问题，如任务调度、资源分配等场景。