洛谷3694 邦邦的大合唱站队

题意

有 $N$ 个人要排队，要求一队的站在一起，共有 $M$ 队。调整队列的方法为让一部分人出队，再回到不同的空位里。求最少要让多少人出队。

$N\le 100000 \ , \ M\le 20$ 。

题解

对每支队伍是否有序状压，用 $f[i]$ 表示状态为 $i$ 时最少的出队人数。

记录第 $j$ 支队伍的人数为 $cnt[j]$ ，设之前排到了第 $l$ 个人，那么现在要排的是 $[l+1,l+cnt[j]]$ ，然后把所有队伍不是 $j$ 的人出队即可。

记录前 $i$ 个人中，第 $j$ 支队伍的人数为 $s[i][j]$ ，那么可以得到方程：

$$f[i]=\min f[i \ xor \ 2^{j-1}]+cnt[j]-(s[r][j]-s[l][j])$$

$r$ 可以通过枚举 $1$ 算出来，$l$ 即为 $r-cnt[j]$ 。

#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]);
}