正题
题目链接:https://www.luogu.com.cn/problem/P3694
题目大意
n
n
n个人，有
m
m
m个队伍，每个人都属于一个队伍。要求叫出一些人来，然后任意插入出来的空隙中使得同一队的人在一起。求最少出列人数。
解题思路
如果知道最终的队列就可以十分容易的计算答案了。考虑一个一个队伍的放入最终序列中，因为
m
m
m十分的小，所以我们可以状压表示排好了的队伍集合，然后用一个前缀和统计在一个区域内每个队伍的人数即可进行
d
p
dp
dp。
时间复杂度
O
(
n
m
+
2
m
m
)
O(nm+2^mm)
O(nm+2mm)
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std
;
int n
,m
,s
[110000][20],wz
[1<<20],f
[1<<20];
int main()
{
scanf("%d%d",&n
,&m
);
for(int i
=1;i
<=n
;i
++){
int x
;scanf("%d",&x
);x
--;
for(int j
=0;j
<m
;j
++)
s
[i
][j
]=s
[i
-1][j
]+(x
==j
);
}
int MS
=1<<m
;
for(int i
=0;i
<MS
;i
++)
for(int j
=0;j
<m
;j
++)
wz
[i
]+=s
[n
][j
]*((i
>>j
)&1);
memset(f
,0x3f,sizeof(f
));f
[0]=0;
for(int i
=1;i
<MS
;i
++){
for(int j
=0;j
<m
;j
++){
int k
=i
^(1<<j
);
if(k
>i
)continue;
f
[i
]=min(f
[i
],f
[k
]+s
[n
][j
]-s
[wz
[i
]][j
]+s
[wz
[k
]][j
]);
}
}
printf("%d",f
[MS
-1]);
}
