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

15303105423 · 发表于 11 小时前

一、题目解读

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

二、解题思路

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

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

2. 预处理：统计每个团队人数cnt[]，并计算前缀和sum[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)。
通过状态压缩与巧妙设计，将问题转化为高效的动态规划模型，适用于团队分配类问题的通用解法。
来源：洛谷P3694题解：动态规划与状态压缩优化解题全解析