题意
有 个人要排队,要求一队的站在一起,共有 队。调整队列的方法为让一部分人出队,再回到不同的空位里。求最少要让多少人出队。
。
题解
对每支队伍是否有序状压,用 表示状态为 时最少的出队人数。
记录第 支队伍的人数为 ,设之前排到了第 个人,那么现在要排的是 ,然后把所有队伍不是 的人出队即可。
记录前 个人中,第 支队伍的人数为 ,那么可以得到方程:
可以通过枚举 算出来, 即为 。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
int n,m,a,s[100005][25],f[1048576],cnt[25];
signed main()
{
n=read(); m=read();
const int M=1<<m;
for (int i=1;i<=n;i++)
{
memcpy(s[i],s[i-1],sizeof(s[i]));
s[i][a=read()]++;
cnt[a]++;
}
memset(f,0x3f,sizeof(f));
f[0]=0;
for (int i=1;i<M;i++)
{
int r=0;
for (int j=0;j<m;j++) r+=(i>>j&1)*cnt[j+1];
for (int j=0;j<m;j++)
{
if (!(i>>j&1)) continue;
int l=r-cnt[j+1];
f[i]=min(f[i],f[i^(1<<j)]+cnt[j+1]-s[r][j+1]+s[l][j+1]);
}
}
return !printf("%d",f[M-1]);
}