洛谷P3694题解：动态规划与状态压缩优化解题全解析
https://www.xinaozhilu.cn/zb_users/upload/2025/07/202507081751957224898633.jpg一、题目解读洛谷P3694题要求解决一个多团队人数分配问题，给定n个元素和m个团队，每个元素属于一个团队，需将元素重新排列，使相邻元素属于不同团队，并最小化调整次数。题目难点在于如何高效处理团队间的空区间与动态规划状态设计。二、解题思路核心思想：采用动态规划+状态压缩。1. 状态设计：使用位掩码（bitmask）表示已处理的团队状态，dp表示当前状态下最小调整次数。2. 预处理：统计每个团队人数cnt[]，并计算前缀和sum（团队i前j个元素的人数）。3. 空区间优化：当团队间存在空区间时，需计算连续未分配团队所需的调整次数。4. 特殊处理：m=1时无需调整，直接输出0。三、解题步骤1. 数据预处理：遍历输入，统计cnt[]并计算sum[][]前缀和。2. 初始化动态规划：dp=0（初始状态），其余状态初始化为INF。3. 状态转移循环：○ 遍历所有状态mask，若当前状态不可达则跳过。○ 计算已排好的长度len（已处理团队人数之和）。○ 遍历未处理团队i，计算区间（当前团队人数区间）。○ 若区间为空（l > r）则跳过；否则计算调整次数cost（区间长度减去实际人数）。○ 更新状态：dp = min(dp + 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, cnt;
int sum; // sum表示前j个元素中i团队的人数
int dp;
void preprocess() {
// 预处理：统计cnt[]和sum[][]
for(int i=1; i<=m; i++) {
for(int j=1; j<=n; j++) {
sum = sum + (a==i); // 累加团队人数
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for(int i=1; i<=n; i++) {
cin >> a;
cnt]++; // 统计每个团队人数
}
// 特判m=1（无需调整）
if(m == 1) {
cout << 0 << endl;
return 0;
}
preprocess();
memset(dp, INF, sizeof(dp)); // 初始化dp数组
dp = 0; // 初始状态：未处理任何团队
// 动态规划主循环
for(int mask=0; mask<(1<<m); mask++) {
if(dp == INF) continue; // 不可达状态跳过
int len = 0; // 当前已排好的长度
for(int i=0; i<m; i++) {
if(mask & (1<<i)) len += cnt; // 累加已处理团队的人数
}
for(int i=0; i<m; i++) {
if(!(mask & (1<<i))) { // 未处理的团队i
int l = len + 1; // 区间左端点（当前团队起始位置）
int r = len + cnt; // 区间右端点（当前团队结束位置）
if(l > r) continue; // 空区间跳过（如团队人数为0）
int cost = (r-l+1) - (sum - sum); // 调整次数：区间长度 - 实际人数
if(dp + cost < dp) {
dp = dp + cost; // 状态转移
}
}
}
}
cout << dp[(1<<m)-1] << endl; // 最终答案：所有团队处理完毕的状态
return 0;
}
五、总结1. 核心技巧：利用位掩码压缩状态，降低动态规划维度；2. 优化点：预处理前缀和避免重复计算，空区间判断减少无效转移；3. 复杂度分析：时间复杂度O(m*2^m)，空间复杂度O(2^m)。通过状态压缩与巧妙设计，将问题转化为高效的动态规划模型，适用于团队分配类问题的通用解法。来源：洛谷P3694题解：动态规划与状态压缩优化解题全解析
页:
[1]