题目分析
首先我们来抓题目里的关键信息：最少、M≤20
那么由此得出做法就是DFS、贪心或DP，我们一一讨论
设计转移方程
转移方程自然就是对于某个乐队，从未排好序到排好序的转移
举个栗子，比如说\(i=(7)_{10}=(111)_2\)，\(j=(3)_{10}=(011)_2\)，那么我们就要从\(f[j]\)转移到\(f[i]\)，也就是将第3号乐队排好序
假如当前的状态为\(i\)（压缩过后），将第\(j\)号乐队排好序，那么就需要从\(i\ xor\ (1<<(j-1))\)这个状态转移而来，也就是第\(j\)位为0时的状态
（为什么位移是\(j-1\)？因为最低位也表示一个乐队，假设\(j=1\)，\(1<<j\)不就等于\((10)_2\)，多移了一位）
接下来我们就要想，如何表示将第\(j\)号乐队排好序需要出列的人数呢？
我们通过“大减小”的方法，首先表示出\(j\)号乐队中所有的人数，再减去实际上不需要出列的人数，就能得到需要出列的人数（具体怎么操作继续往下看）
值得注意的是：我们默认直接把\(j\)乐队排在已经排好的乐队后面，由于我们状压DP中的状态循环会把每种i的情况都跑一遍，所以这样做是不会漏情况的
例如：共有3个乐队，\(j=2\)
\(i=(010)_2\) 由\((000)_2\)转移而来 代表把所有2号乐队的排最前面
\(i=(011)_2\) 由\((001)_2\)转移而来 代表先排1号乐队，再把所有2号乐队跟后面
\(i=(110)_2\) 由\((100)_2\)转移而来 代表先排3号乐队，再把所有2号乐队跟后面
\(i=(111)_2\) 由\((101)_2\)转移而来 代表先排好1、3号乐队（而这其中具体是先排1号乐队还是先排3号乐队就是\(j=1\)和\(j=3\)时的事了）最后排2号乐队
如此就可以把对于\(j=2\)的所有情况涉及，\(j=1\)、\(j=3\)同理，最后就覆盖了所有情况
那么我们就可以写出状态转移方程了：
\[f[i]=min\{f[i\ xor\ (j-1)]+(r-l+1)-sum[l,r][j]\} \]这个方程当中，\(l\)和\(r\)分别代表插到后面的\(j\)乐队的左右区间，\(r-l+1\)表示这区间内有多少人（其实就是第\(j\)号乐队有多少人），\(sum[l,r][j]\)就代表\(l\)到\(r\)这个区间内属于\(j\)乐队的人数
举个例子，此时\(j=2\)，要从\((00)_2\)转移到\((10)_2\)，此时\(r=1\)，\(l=3\)。那么运用“大减小”，本来需要把前三个数（\(r-l+1=3\)）都踹出队，但我们发现有一个数是队友（\(sum[l,r][j]=1\)），所以就不用踹它了，最后得出只需要踹两个人
特别注意！有人会问：这时候怎么只有前面两个1出队，后面两个2呢？
其实这时候我们只用管前面\([l,r]\)这个区间，等到后面要从\((10)_2\)转移到\((11)_2\)时，会把后面这两个2给出队的
如果现在就把后面的2给踢了，甚至有可能导致后面的2多次出队，而且万一后来发现当前状态所对应的最优解不是把前面的1和后面的2踢掉并交换，那怎么办？所以这也体现出了DP的无后效性，你处理\(j=2\)的状态就只关\(j=2\)所对应的区间，和其他区间无关
代码实现
对于前面推出来的转移方程
\[f[i]=min\{f[i\ xor\ (j-1)]+(r-l+1)-sum[l,r][j]\} \]不难发现，其实\(r-l+1\)其实就是第\(j\)号乐队的人数，所以我们可以在写代码的时候用一个数组\(num[j]\)来记录每一个乐队的人数；而后面的\(sum[l,r][j]\)可以用前缀和优化；并且可以发现\(l\)和\(r\)其实是与当前的状态有关（比如说现在状态为\((100)_2\)，那么\(l\)就等于3号乐队人数+1，\(r\)就等于3号乐队人数+第\(j\)号乐队人数），因此可以用一个数组\(len[i]\)记录状态为\(i\)时的总人数。
于是我们得到最终的式子：
最终得到代码如下：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5,MAXF=(1<<20)+5,MAXM=22;
int n,m,team[MAXN],f[MAXF],num[MAXM],len[MAXF],sum[MAXN][MAXM];
int main(){
ios::sync_with_stdio(false);
memset(f,0x3f,sizeof(f));
memset(len,0,sizeof(len));
memset(sum,0,sizeof(sum));
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
sum[i][j]=sum[i-1][j];
cin>>team[i];//属于哪个队
num[team[i]]++;//队有多少人
sum[i][team[i]]++;//有多少人时几队有几人
}
int dp=1<<m;//(1<<m)-1的二进制为m个1
for(int i=1;i<dp;i++){
for(int j=1;j<=m;j++){
if(i&(1<<(j-1))) len[i]+=num[j];//状态为i时有多少人
}
}
f[0]=0;
for(int i=1;i<dp;i++){
for(int j=1;j<=m;j++){
if(i&(1<<(j-1))){
int pre=i^(1<<(j-1));
f[i]=min(f[i],f[pre]+num[j]-(sum[len[i]][j]-sum[len[pre]][j]));
}
}
}
cout<<f[dp-1]<<endl;
return 0;
}
小细节： 加减乘除模运算优先级比位运算高，\(1<<j-1\)的意思是\(1<<(j-1)\)，不是\((1<<j)-1\)！！！
标签：洛谷,大合唱,sum,乐队,P3694,排好序,人数,转移,DP From： https://www.cnblogs.com/SkyNet-PKN/p/17135640.html