P7519 [省选联考 2021 A/B 卷] 滚榜解题报告

解题报告

P7519 [省选联考 2021 A/B 卷] 滚榜解题报告：

更好的阅读体验

题意

给定$n$支队伍，每支队伍有权值$a_i$。给定$m$，将$m$分成若干个数之和，按不降顺序分配给$n$个队伍，已知每次分配都会让分配给的队伍权值变为最大（权值相同比较编号大小，小的优先），求分配方案数。

$1\leqslant n\leqslant 13,1\leqslant m\leqslant 500$

分析

很简单的状压dp+费用提前，但考场降智了，没想到。

设$f_{i,j,k}$为当前分配完的队伍集合为$i$，上一个分配的队伍为$j$，一共消耗的权值大小为$k$的方案数，可是由于分配权值的顺序必须不降，所以还得带上另一个参数来表示上一次分配的权值，可是这样就是$O(2^nn^2m^2)$的了，比阶乘还劣。

考虑表示出或消除这个参数，根据上面的定义表示出这个参数比较难，因此我们想一想如何将这个参数的费用消除掉。

我们先想一想当我们确定了分配顺序应该怎么判断：我们按照顺序给每个队伍分配最少的权值，最后如果分配失败就说明方案失败，否则可以直接把所有剩下权值分配给最后一个队伍。

我们考虑剩下的权值不分配给最后一个队伍的情况，这时可以对于一个队伍后缀增加一个不递减的权值序列，而对这个序列差分后可以知道这个权值序列可以分成若干次给某个后缀加上相同的权值。

这提醒了我们使用费用提前，$f_{0,0,0}$转移到$f_{i,j,k}$（其中$i$集合仅含$j$）时，不难发现需要给$j$队伍增加权值$a_p-a_j+[p<j]$（设一开始权值最大的队伍为$p$），而根据上面的思考可以知道这个权值在以后每个队伍都需要进行分配，那么我们直接将权值乘$n$，提前计算费用即可。

同理，对$f_{i,j,k}$转移到$f_{i',j',k'}$，我们对于当前队伍需要增加$a_j-a_{j'}+[j<j']$的权值，我们将权值乘$|i|$就可以消除后续的贡献。

时间复杂度：$O(2^nn^2m)$，用$\text{lowbit}$来枚举可以卡卡常。

代码

#include<stdio.h>
#define lowbit(x) x&-x
const int maxn=13,maxm=505,maxk=(1<<maxn);
int n,m,k,maxx,maxp;
int a[maxn+1],tot[maxk],p[maxk];
long long ans;
long long f[maxk][maxn+1][maxm];
inline int max(int a ,int b){
    return a>b? a:b;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]),p[1<<(i-1)]=i;
        if(a[i]>maxx)
            maxx=a[i],maxp=i;
    }
    k=(1<<n)-1,tot[0]=0;
    for(int i=1;i<=k;i++)
        tot[i]=tot[i>>1]+(i&1);
    for(int i=1;i<=n;i++){
        int cost=n*(maxx-a[i]+(maxp<i));
        if(cost<=m)
            f[1<<(i-1)][i][cost]=1;
    }
    for(int i=1;i<k;i++)
        for(int j=i;j;j-=lowbit(j))
            for(int s=0;s<=m;s++){
                int v=lowbit(j),now=p[v];
                if(f[i][now][s]==0)
                    continue;
                for(int t=1;t<=n;t++)
                    if(((i>>(t-1))&1)==0){
                        int cost=s+(n-tot[i])*max(a[now]-a[t]+(now<t),0);
                        if(cost<=m)
                            f[i|(1<<(t-1))][t][cost]+=f[i][now][s];
                    }
            }
    for(int i=0;i<=n;i++)
        for(int j=1;j<=m;j++)
            ans+=f[k][i][j];
    printf("%lld\n",ans);
    return 0;
}

省选联考A卷全部题解可见：2021省选联考A卷解题报告