[题目传送门](https://www.luogu.com.cn/problem/P4798) 比较简单的dp题。第一眼看着比较像数位dp，但有比数位dp常用的记忆化搜索更简便的做法。设 [imath]dp_{i,j}[/imath] 表示指当前有 [imath]i[/imath] 人，第一个人的队伍编号不大于 [imath]j[/imath] 时的方案数。那么如果此时新加入一个人，他所在队伍只有两种情况，第一种情况为原有队伍中的一个，第二种为原有队伍数加一。那么，就可以推出转移方程： [math] dp_{i,j}=dp_{i-1,j}*(j-1)+dp_{i-1,j+1} [/math] 然后，就是数位dp的流程了。枚举第 [imath]i[/imath] 个人的队伍 ,然后根据数位限制的情况累加可能的情况数。但是由于空间限制的原因，需要用滚动数组(详见代码)。 ### 代码 ```cpp #include using namespace std; using ll=long long; const int N=10005; const int mod=1000007; ll n,a[N],dp[N],maxn[N],ans; int main() { cin>>n; for(int i=1;i>a[i]; dp[i]=1; maxn[i]=max(maxn[i-1],a[i]);//前i个队伍的最大值 } for(int i=n;i>=1;i--){ ans+=dp[maxn[i-1]]*(a[i]-1)%mod; for(int j=1;j

洛谷P4798 [CEOI 2015] 卡尔文球锦标赛 (Day1) 题解

Yichen

题目传送门

比较简单的dp题。

第一眼看着比较像数位dp，但有比数位dp常用的记忆化搜索更简便的做法。

设 dp_{i,j} 表示指当前有 i 人，第一个人的队伍编号不大于 j 时的方案数。那么如果此时新加入一个人，他所在队伍只有两种情况，第一种情况为原有队伍中的一个，第二种为原有队伍数加一。

那么，就可以推出转移方程：
dp_{i,j}=dp_{i-1,j}*(j-1)+dp_{i-1,j+1}

然后，就是数位dp的流程了。枚举第 i 个人的队伍 ,然后根据数位限制的情况累加可能的情况数。

但是由于空间限制的原因，需要用滚动数组(详见代码)。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=10005;
const int mod=1000007; 

ll n,a[N],dp[N],maxn[N],ans;

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		dp[i]=1;
		maxn[i]=max(maxn[i-1],a[i]);//前i个队伍的最大值 
	}
	for(int i=n;i>=1;i--){
		ans+=dp[maxn[i-1]]*(a[i]-1)%mod; 
		for(int j=1;j<=i;j++)
			dp[j]=(dp[j]*j+dp[j+1])%mod;//滚动数组 
	}
	cout<<ans%mod+1;//当前ans是多少方案比n小，因此需要加上1 
	
	return 0;
 }