洛谷P3694题解：动态规划与状态压缩优化解题全解析

一、题目解读

洛谷P3694题要求解决一个多团队人数分配问题，给定n个元素和m个团队，每个元素属于一个团队，需将元素重新排列，使相邻元素属于不同团队，并最小化调整次数。题目难点在于如何高效处理团队间的空区间与动态规划状态设计。

二、解题思路

核心思想：采用动态规划+状态压缩。

1. 状态设计：使用位掩码（bitmask）表示已处理的团队状态，dp[mask]表示当前状态下最小调整次数。

2. 预处理：统计每个团队人数cnt[]，并计算前缀和sum[i][j]（团队i前j个元素的人数）。

3. 空区间优化：当团队间存在空区间时，需计算连续未分配团队所需的调整次数。

4. 特殊处理：m=1时无需调整，直接输出0。

三、解题步骤

1. 数据预处理：遍历输入，统计cnt[]并计算sum[][]前缀和。

2. 初始化动态规划：dp[0]=0（初始状态），其余状态初始化为INF。

3. 状态转移循环：

○ 遍历所有状态mask，若当前状态不可达则跳过。

○ 计算已排好的长度len（已处理团队人数之和）。

○ 遍历未处理团队i，计算区间[l,r]（当前团队人数区间）。

○ 若区间为空（l > r）则跳过；否则计算调整次数cost（区间长度减去实际人数）。

○ 更新状态：dp[mask | (1<<i)] = min(dp[mask] + cost)。

4. 最终答案：dp[(1<<m)-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], cnt[MAXM+2];  
int sum[MAXM+2][MAXN]; // sum[i][j]表示前j个元素中i团队的人数  
int dp[1<<MAXM];  

void preprocess() {  
    // 预处理：统计cnt[]和sum[][]  
    for(int i=1; i<=m; i++) {  
        for(int j=1; j<=n; 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();  
    memset(dp, INF, sizeof(dp)); // 初始化dp数组  
    dp[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]; // 累加已处理团队的人数  
        }  

        for(int i=0; i<m; i++) {  
            if(!(mask & (1<<i))) { // 未处理的团队i  
                int l = len + 1; // 区间左端点（当前团队起始位置）  
                int r = len + cnt[i+1]; // 区间右端点（当前团队结束位置）  
                if(l > r) continue; // 空区间跳过（如团队人数为0）  

                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. 核心技巧：利用位掩码压缩状态，降低动态规划维度；

2. 优化点：预处理前缀和避免重复计算，空区间判断减少无效转移；

3. 复杂度分析：时间复杂度O(m*2^m)，空间复杂度O(2^m)。

通过状态压缩与巧妙设计，将问题转化为高效的动态规划模型，适用于团队分配类问题的通用解法。