P3694 邦邦的大合唱站队

## 题目链接 [点我跳转](https://www.luogu.com.cn/problem/P3694) ## 题目大意 >$N$ 个人排成一列，每个人都有自己所属的乐队，其中第 $i$ 个人一开始所在的位置为 $i$ > >你可以从队列中抽出任意数量的人，抽出后他们所在的位置将为空，之后你可以再把他们放进任意空位置 > >现要求同一个乐队的人必须站在一起，问最少要抽出多少人 ## 解题思路 >定义 $cnt[i]$ 表示乐队 $i$ 的总人数 > >定义 $dp[i]$ 表示{已处理好该状态所对应的所有乐队}的最少出列个数 > >对于状态 $110$ (二进制) >$dp[110]$ 可以由 $dp[100]$ 和 $dp[010]$ 转移得到 > >而 $dp[100]$ 率先处理好的乐队是 $3$ > >可以认为率先处理好乐队 $3$ 就是把该乐队成员放在 $1$ ~ $cnt[3]$ 的位置上 > >$dp[010]$ 率先处理好的乐队是 $2$ > >可以认为率先处理好乐队 $2$ 就是把该乐队成员放在 $1$ ~ $cnt[2]$ 的位置上 > >那么 $dp[110]$ 就可以由{先处理 $3$ 再处理 $2$} 和 {先处理 $2$ 再处理 $3$} 两种情况取最优得到 > >同理 $dp[111]$ 是由乐队 $1$、乐队 $2$、乐队 $3$ 从第一个位置开始任意摆放所得到的最优解 > >所以我们无需再考虑摆放顺序 > >而将第 $i$ 个乐队成员摆放在 $[L , R]$ 的代价 $=$ 该区间长度 $-$ 该区间第 $i$ 个乐队的人的个数 > >这步我们可以用前缀和维护 ## AC_Code ```cpp #include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int dp[1 << 20]; int cnt[N] , sum[N][21]; int a[N]; int get(int l , int r , int x){ return (r - l + 1) - (sum[r][x] - sum[l - 1][x]); } signed main() { memset(dp , 0x3f3f , sizeof(dp)) , dp[0] = 0; int n , m; cin >> n >> m; for(int i = 1 ; i <= n ; i ++) { cin >> a[i]; for(int j = 1 ; j <= m ; j ++) sum[i][j] = sum[i - 1][j]; sum[i][a[i]] ++ ; cnt[a[i]] ++ ; } int up = (1 << m) - 1; for(int i = 1 ; i <= up ; i ++) { int R = 0; for(int j = 0 ; j <= m - 1 ; j ++) if(i >> j & 1) R += cnt[j + 1]; for(int j = 0 ; j <= m - 1 ; j ++) if(i >> j & 1) { int k = i - (1 << j); int L = R - cnt[j + 1] + 1; dp[i] = min(dp[i] , dp[k] + get(L , R , j + 1)); } } cout << dp[up] << '\n'; return 0; } ```