题解 P7519 [省选联考 2021 A/B 卷] 滚榜
白鲟
2021-04-15 17:02:12
## 前言
纪念一下这场爆炸的省选唯一 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 上可通过。
```cpp
#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;
}
```