洛谷3694 邦邦的大合唱站队

编辑文章

题意

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

N100000 , M20N\le 100000 \ , \ M\le 20

题解

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

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

记录前 ii 个人中,第 jj 支队伍的人数为 s[i][j]s[i][j] ,那么可以得到方程:

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

rr 可以通过枚举 11 算出来,ll 即为 rcnt[j]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]);
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空