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

· · 题解

前言

纪念一下这场爆炸的省选唯一 AC 的题目。

同时是第一次在正式考场上 AC 动态规划。

同时是第一次在正式考场上 CE（还是本应 AC 的 Day1 T1）。

大概是本场第三简单的题。

应该比去年 Day2 T1 简单。

分析

看了一眼范围估计是状压。

开始分析的时候容易想到设计状态为 f(S,i,j,k)，即前 |S| 位为 S 内元素、第 |S| 位为 i、已选 b_i 总和为 j、上一个 b_i 为 k 的方案总数，但始终甩不掉枚举 b_i 的和与上一个 b_i 的值的 m^2 循环。

冷静看题。发现只用求排名的总方案数，而与 b_i 分配方式无关。可以得到的启发是寻找 b_i 的最佳分配方式。

对于某一确定的排列方式 a_1,a_2,\cdots,a_n，贪心地分配使得每个位置的 b_i 尽量小的方式易得：若当前的 a_i 大于 a_{i-1}，为了维护 b_i 不降，使得 b_i=b_{i-1}，否则 b_i=b_{i-1}+a_{i-1}-a_i。

根据这一结论，直接使用全排列可以获得 60 pts 的好成绩。

回到状压。考虑对贡献进行简单变形：\sum{b_i}=\sum{\max(a_{i-1}-a_i,0)}(n-i+1)，如此可以甩掉枚举上一个 b_i 的值这一步。设 f(S,i,j) 表示前 |S| 位为 S 内元素、第 |S| 位为 i、已选总贡献为 j 的方案总数，在枚举状态的同时枚举下一个选的数，容易写出方程式。

最后统计 f(U,i,j) 的和即可。

时间复杂度为 \operatorname{O}(2^nn^2m)。可通过使用 \operatorname{lowbit} 枚举元素等方式略微卡常。

上述方法忽略的细节是相等时的按编号排序，实现时应注意。

代码

upd on 2021.4.24

根据 UOJ 数据修复了代码实现的一点小问题，目前在 UOJ 上可通过。

#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=13,maxm=500;
int n,m,all,t,a[maxn+1],no[1<<maxn|1];
long long f[1<<maxn|1][maxn+1][maxm+1],ans;
inline int lowbit(int x)
{
    return x&(-x);
}
int main()
{
    scanf("%d%d",&n,&m);
    all=(1<<n)-1;
    a[0]=-1;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        if(a[i]>a[t])
            t=i;
        no[1<<(i-1)]=i;
    }
    for(int i=1;i<=n;++i)
    {
        int target=n*(a[t]-a[i]+(t<i));
        if(target<=m)
            f[1<<(i-1)][i][target]=1;
    }
    for(int i=1;i<all;++i)
    {
        int popcount=0;
        for(int j=1;j<=maxn;++j)
            if(i&(1<<(j-1)))
                ++popcount;
        for(int t=i;t;t-=lowbit(t))
            for(int sum=0;sum<=m;++sum)
            {
                int pos=no[lowbit(t)];
                for(int j=1;j<=n;++j)
                    if(!(i&(1<<(j-1))))
                    {
                        int target=sum+(n-popcount)*max(0,(pos<j)+a[pos]-a[j]);
                        if(target<=m)
                            f[i|(1<<(j-1))][j][target]+=f[i][pos][sum];
                    }
            }
    }
    for(int i=0;i<=m;++i)
        for(int j=1;j<=n;++j)
            ans+=f[all][j][i];
    printf("%lld",ans);
    return 0;
}