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

· · 题解

哎，考场上面连题都没有读懂，基本上把这次省选葬了。

主要是讲思考的思路。

考虑到数据范围很小，n \leq 13，不难想到状压 dp。

进行状态设计。

既然是状压不可能没有 O(2^n) 一维。

因为我们 b_i 的决定会和上一个人有关，显然储存上一个人是谁这一维无可避免，O(n)。

剩下的一个比较好想的做法是，保存上一个人的 b_i 是多少，已经当前已经多用了多少题。这样有两个 O(m) 级别的信息。

暴力即为暴力转移，时间复杂度 O(2^nn^2m^2) 或者 O(2^nnm^2)，空间复杂度 O(2^nnm^2)。

注意到我们统计的是排名的方案数，跟具体的 b_i 是无关的，也就是说，保存上一个人的 b_i 是无效信息。

考虑将这一维删去，也就是说我们需要通过一些操作使得这一维的信息能够被表示或者忽略。

被表示估计不太行。注意到 b 序列单调不降，考虑差分，将新数列记为 \Delta。因为 b 序列单调不降，所以 \forall i \in [1,n],\Delta_i \geq 0。

注意到 \Delta_i 会使得所有 j \geq i 的 b_j 增加 \Delta_i。考虑每次加入 \Delta_i 的时候把后面的影响一并处理。

具体想法是，我们将 i 滚榜的时候，不用知道上一个的 b 到底是多少也能满足 b 不降。那么我们每次在处理的时候每次加入 \Delta_i，后面的所有 b 也同时加上 \Delta_i。这样我们就相当于枚举差分值，显然是可以满足 b 单调不降的条件的。只需要考虑单纯的，不考虑 b_i 的从 u 转移到 v 的最少的题数了。

也许这个东西叫做费用提前计算？

考虑实现，预处理一个数组 c_{i,j} 表示上一个是 i，这次滚榜到 j 需要的最小的 b_i。至于不用考虑上一个 i 加上的 b_i 的原因因为我们在上面的做法中规避了这个问题，不理解还可以返回去看。代码写起来就很简单了。

#include<bits/stdc++.h>
using namespace std;
int lowbit(int x){return x&(-x);}
int popcount(int x){int ans=0;while(x)  x-=lowbit(x),++ans;return ans;}
int dp[(1<<13)+5][14][505],n,m,a[14],c[14][14];
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i)   scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)   for(int j=1;j<=n;++j)   c[i][j]=max(0,a[i]-a[j]+int(i<j)),c[0][j]=max(c[0][j],c[i][j]);
    dp[0][0][0]=1;
    for(int S=0;S<(1<<n);++S)
    {
        if(S==lowbit(S))
        {
            int pos=0;
            for(int i=1;i<=n;++i)   if((S>>(i-1))&1 && (pos=i)) break;
            if(n*c[0][pos]<=m)  dp[S][pos][n*c[0][pos]]=1;
        }
        else
        {
            for(int i=1;i<=n;++i)
            {
                if((S>>(i-1))&1)
                {
                    int T=S^(1<<(i-1));
                    int v=i;
                    for(int j=1;j<=n;++j)
                    {
                        if((T>>(j-1))&1)
                        {
                            int u=j;
                            int pct=n-popcount(T);
                            for(int k=c[u][v]*pct;k<=m;++k) dp[S][v][k]+=dp[T][u][k-c[u][v]*pct];
                        }
                    }
                }
            }
        }
    }
    long long ans=0;
    for(int i=1;i<=n;++i)   for(int j=1;j<=m;++j)   ans+=dp[(1<<n)-1][i][j];
    printf("%lld",ans);
    return 0;
}