[luoguP3694] 邦邦的大合唱站队／签到题（状压DP）

来自kkk的题解：

70分做法：枚举每个学校顺序，暴力。

100分：状压dp。从队列头到尾DP，

状态：f[i]表示i状态下最小的出列（不一致）的个数。

比如f[1101]表示从头到位为1/3/4乐队的偶像的最小出列个数。

f[i]=min(f[i\ xor\ 2^j]+num[j]-(sum[length][j]-sum[length-num[j]][j]));f[i]=min(f[i xor 2j]+num[j]−(sum[length][j]−sum[length−num[j]][j]));

j表示团队编号，sum表示某种团队的前缀和，length表示到此已经排到的长度。

#include <cstdio>

#include <cstring>

#include <iostream>

#define M 21

#define N 100001

#define min(x, y) ((x) < (y) ? (x) : (y))

int n, m, S, cnt;

int sum[N][M], num[M], f[1 << M];

inline int read()

{

	int x = 0, f = 1;

	char ch = getchar();

	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;

	for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';

	return x * f;

}

int main()

{

	int i, j, x;

	n = read();

	m = read();

	memset(f, 127, sizeof(f));

	for(i = 1; i <= n; i++)

	{

		x = read();

		num[x]++;

		for(j = 1; j <= m; j++)

			sum[i][j] = sum[i - 1][j] + (x == j);

	}

	f[0] = 0;

	for(i = 1; i < (1 << m); i++)

	{

		S = 0;

		for(j = 1; j <= m; j++)

			if(i & (1 << j - 1))

				S += num[j];

		for(j = 1; j <= m; j++)

			if(i & (1 << j - 1))

			{

				cnt = num[j] - sum[S][j] + sum[S - num[j]][j];

				f[i] = min(f[i], f[i ^ (1 << j - 1)] + cnt);

			}

	}

	printf("%d\n", f[(1 << m) - 1]);

	return 0;

}