自动搬运

查看原文

来自洛谷，原作者为

	rhn7 洛谷用户数：1789309

搬运于2025-08-24 22:03:44，当前版本为作者最后更新于2024-01-23 11:59:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

第一眼看上去像是数位 dp，实际比数位 dp 简单很多。

设当前有 $i$ 人，分成了 $T$ 个队，新来了一个人，那这个人要么在 $T$ 个队中的一个，要么新开启了第 $T+1$ 个队，也就是这个人所在的队伍编号 $\le T+1$。

知道这个就可以开始 dp 了，我们设 $dp_{i,j}$ 表示有 $i$ 个人，第一个人的队伍编号 $\le j$，按刚才说的转移即可：

$dp_{i,j}=dp_{i-1,j} × (j-1) + dp_{i-1,j+1}$

接下来就是类似数位 dp 的试填法，枚举第 $i$ 个人的队伍 $j$。

如果 $j < a_{i}$，后面 $n-i$ 个人可以随便选，也就是 $dp_{n-i,max(j+1,mx+1)}$。

如果 $j = a_{i}$，往下考虑第 $i+1$ 个人。

这道题的数据又卡空间又卡时间，所以要用滚动数组优化，本蒟蒻的代码跑的非常慢，大佬就凑合看吧：

#include<iostream>
using namespace std;
typedef long long ll;
ll n,i,j,k,x,ans,p=1000007,mx[10005],a[10005],dp[10005];
int main(){
	cin>>n;
	for(i=1;i<=n;i++) dp[i]=1,cin>>a[i],mx[i]=max(mx[i-1],a[i]);//前缀最大值 
	for(i=n;i;i--){
		//第i个人的队伍编号最多是mx[i-1]+1 
		for(j=1;j<=min(mx[i-1]+1,a[i]-1);j++) ans=(ans+dp[max(j+1,mx[i-1]+1)])%p;
		for(j=1;j<=i;j++) dp[j]=((j-1)*dp[j]+dp[j+1])%p;//滚动数组优化 
	}
	cout<<(ans+1)%p;//当前ans是多少方案比a小，ans+1后就是排名了 
	return 0;
}