夏晓光(loveJY)的博客

害

挺简单的,自己就切掉了??

没有构造的思想,首先问题变成我们要把这些偶像团队排成一列,然后问最小的前后序列差异值

显然M!是不现实的,所以我们可以考虑状压优化全排列

一下就能猜出复杂度是$O(m2^m)$,那么我们dp状态撑死了两维,2^m?

注意到我们本质上是在找一个顺序使得每个团队都加入分配好集合中,所以这个$2^m$就表示每个团队是否加入集合中

然后我们把这$2^m$个S按照有多少个01排序,我们就能按照此顺序依次枚举,然后再去枚举下一个放进去的团队,由于我们已经知道了有多少个团队你分配好了,所以我们也能知道对应这个团队放入的区间

计算代价....其实你会发现这个区间内原属于这个团队的不用动外其他的位置都要移走....

就是$sum-sum_r-sum_{l-1}$

可以看成区间其他位置全动然后之后一定会有某次算上其他位置的

code:

#include<bits/stdc++.h>
#define mkp(x,y) (make_pair(x,y))
#define fi first
#define se second
using namespace std;
const int MAXN = 1e5 + 7;
const int MAXM = 21;
const int MAXS = 2097152;
int n, m, a[MAXN], sum[MAXN][MAXM];
int dp[MAXS], T, cnt[MAXS], nwS[MAXS];
pair<int, int> que[MAXS];

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		sum[i][a[i]]++;
		for(int j = 1; j <= m; ++j) {
			sum[i][j] += sum[i - 1][j];
			// printf("i:%d j:%d sum:%d\n", i, j, sum[i][j]);
		}
	}
	int MAXS = (1 << m) - 1;
	for(int S = 0; S <= MAXS; ++S) {
		for(int i = 0; i < m; ++i) {
			if(S >> i & 1) {
				cnt[S]++;
				nwS[S] += sum[n][i + 1];
				// printf("%d????%d %d\n", nwS[S], sum[n][i + 1], a[i + 1]);
			}
		}
		que[++T] = mkp(cnt[S], S);
		// printf("%d %d %d?\n", S, cnt[S], nwS[S]);
	}
	sort(que + 1, que + T + 1);
	memset(dp, 0x3f3f3f3f, sizeof(dp));
	dp[0] = 0;
	for(int k = 1; k <= T; ++k) {
		int nS = que[k].se;
		// int nV = que[k].fi;
		int nL = nwS[nS] + 1, nR, cost; //现在的
		for(int i = 1; i <= m; ++i) {
			if(nS >> (i - 1) & 1)continue; //已经加入
			nR = nL + sum[n][i] - 1;
			cost = (sum[n][i]) - (sum[nR][i] - sum[nL - 1][i]);
			// printf("%d %d %d %d %d %d %d>>>???\n", nS, i, nL, nR, cost, dp[nS], dp[nS | (1 << (i - 1))]);
			dp[nS | (1 << (i - 1))] = min(dp[nS | (1 << (i - 1))], dp[nS] + cost);
		}
	}
	printf("%d\n", dp[MAXS]);
	return 0;
}