数据约定：$N\le 10^5,M\le 20$

思路

对于最终排好的状态，如果我们枚举排在最后一位的团队编号 $j$，可以发现：如果这个团队总共有 $x$ 人的话，那么 $[n-x+1,n]$ 一定都是团队 $j$ 的人，那么 $[1,n-x]$ 就是一个子状态

我们可以定义 $dp[S]$ 为已经排好队的团队集合需要的最少出队人数（这个排好队是指从 $1$ 号位开始排，不在集合里的那些团队先不管，都放在后面），那么对于当前状态 $S$，我们枚举最后一个团队 $j$，利用子状态转移即可。提前预处理每个团队的前缀和就可以达到 $O(m{2}^m)$ 的复杂度

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;const int INF=0x3f3f3f3f;
const long long INFLL=1e18;typedef long long ll;const int N = 100050;int dp[1 << 20];
int sum[21][N];
int a[N];
int num[1 << 20]; //状态i下排好的人数int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int n, m;std::cin >> n >> m;fore(i, 1, n + 1){std::cin >> a[i];--a[i];fore(j, 0, m) sum[j][i] = sum[j][i - 1];++sum[a[i]][i];}fore(S, 1, 1 << m)fore(j, 0, m)if(S >> j & 1)num[S] += sum[j][n];memset(dp, INF, sizeof(dp));dp[0] = 0;fore(S, 1, 1 << m)fore(j, 0, m)if(S >> j & 1){int l = num[S - (1 << j)], r = num[S];dp[S] = std::min(dp[S], dp[S - (1 << j)] + sum[j][n] - sum[j][r] + sum[j][l]);}std::cout << dp[(1 << m) - 1];return 0;
}