题解 P4798 [CEOI2015 Day1] 卡尔文球锦标赛

· · 题解

第一眼看上去像是数位 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;
}