自动搬运

查看原文

来自洛谷，原作者为

	白鲟 AFO|Und da warst Du

搬运于2025-08-24 22:30:39，当前版本为作者最后更新于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 上可通过。

#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;
}