题解：P14364 [CSP-S 2025] 员工招聘 / employ（民间数据）

观察数据范围发现可以

O(n^3)

，考虑dp。

设

dp_{i,j,k}

表示已经过了

i

天，已经有

j

个人被拒绝或放弃，前

i

天中有

k

个人满足

c_k\le j

时的方案数，不考虑 $c_i> j$ 的人之间的差别。

设

cnt_i

表示，

pre_i

表示其前缀和。

考虑从

dp_{i,j,k}

转移：

若 $s_{i+1}=0$

显然要转移到 $dp_{i+1,j+1,k^\prime}$ （ $k^\prime$ 的范围有多个限制，详见代码）

先不考虑第 $i+1$ 天的人，由于之前没有区分 $c_i=j+1$ 的人和 $c_i> j+1$ 的人，现在需要另外计算这部分的贡献，即 $new=dp_{i,j,k}\times \begin{pmatrix} i-k \\ k^\prime-k \end{pmatrix}\begin{pmatrix} cnt_{j+1} \\ k^\prime-k \end{pmatrix}(k^\prime-k)!$ （如果dp状态时考虑了所有人的差别，这里就不好转移），然后根据第 $i+1$ 天的人分类讨论：
- $\le j+1$ ， $dp_{i+1,j+1,k^\prime+1}\leftarrow new\times (pre_{j+1}-k^\prime)$
- $> j+1$ ， $dp_{i+1,j+1,k^\prime}\leftarrow new$
若 $s_{i+1}=1$

这次先分类讨论：
- $> j$ ，直接 $dp_{i+1,j,k}\leftarrow dp_{i,j,k}$
- $\le j$ ，和上面一样处理后 $dp_{i+1,j+1,k'+1}\leftarrow new\times (pre_j-k)$

注意计算答案时要算上未区分的人的贡献。

时间复杂度：

转移复杂度 $O(cnt_{j+1})$ ，而 $\sum cnt_j=n$ ，所以总复杂度 $O(n^3)$ ，可以通过本题。

空间用类似01背包的方式去掉一维即可。

代码

有一些边界情况要注意

CPP

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,N=505;
long long f[N],g[N],inv[N];
int n,m,cnt[N],pre[N],dp[N][N];
char s[N];

int main()
{
    scanf("%d %d",&n,&m);
    f[0]=f[1]=g[0]=g[1]=inv[1]=1;
    for(int i=2;i<=n;i++)
    {
        f[i]=f[i-1]*i%mod;
        inv[i]=inv[mod%i]*(mod-mod/i)%mod;
        g[i]=g[i-1]*inv[i]%mod;
    }
    scanf("%s",s+1);
    for(int i=1,c;i<=n;i++)
    {
        scanf("%d",&c);
        cnt[c]++;
    }
    pre[0]=cnt[0];
    for(int i=1;i<=n;i++)pre[i]=pre[i-1]+cnt[i];
    dp[0][0]=1;
    for(int i=0;i<n;i++)
    {
        for(int j=i;j>=0;j--)
        {
            for(int k=pre[j];k>=0;k--)
            {
                int now=dp[j][k];
                dp[j][k]=0;
                if(s[i+1]=='0')
                {
                    for(int k2=max(k,i-(n-pre[j+1]));k2<=k+cnt[j+1]&&k2<=i;k2++)
                    {
                        const int tot=i-k,ths=k2-k,num=cnt[j+1];
                        const long long x=f[tot]*g[ths]%mod*g[tot-ths]%mod*f[num]%mod*g[num-ths]%mod;
                        if(j+1!=n&&pre[j+1]-k2!=n-i)dp[j+1][k2]=(dp[j+1][k2]+x*now)%mod;
                        dp[j+1][k2+1]=(dp[j+1][k2+1]+x*now%mod*(pre[j+1]-k2))%mod;
                    }
                }
                else
                {
                    for(int k2=max(k,i-(n-pre[j+1]));k2<=k+cnt[j+1]&&k2<=i;k2++)
                    {
                        const int tot=i-k,ths=k2-k,num=cnt[j+1];
                        const long long x=f[tot]*g[ths]%mod*g[tot-ths]%mod*f[num]%mod*g[num-ths]%mod;
                        dp[j+1][k2+1]=(dp[j+1][k2+1]+x*now%mod*(pre[j]-k))%mod;
                    }
                    if(pre[j]-k!=n-i)dp[j][k]=now;
                }
            }
        }
    }
    int ans=0;
    for(int j=0;j<=n-m;j++)
    {
        const int k=pre[j];
        ans=(ans+dp[j][k]*f[n-k])%mod;
    }
    printf("%d",ans);
    return 0;
}

题解：P14364 [CSP-S 2025] 员工招聘 / employ（民间数据）

文章操作

代码

相关推荐

评论

题解：P14364 [CSP-S 2025] 员工招聘 / employ（民间数据）