NOIOJ 比赛排名 题解

题目描述

N个人参加比赛,问有多少种排名情况,允许出现并列的情况

输入

输入一个数字N,N小于200
本题有多组数据,请做到-1结束

输出

输出有多少种排名情况

样例输入

2
-1

样例输出

3

数据范围限制

1
2
3
4
5
6
7
8
9
10
11
12
/*
这题没有具体代码,简说思路:
f(m,n)={  //m个人,n种名次
m!,m==n; //当k个人有k种名次时,恰好为全排列
1,n==1; //当只有1个名次时,所有人必须全部并列
n*f(m-1,n)+n*f(m-1,n-1) //动规转移方程,下面详细说
}
//第一个参数必为m-1,因为此时刚刚新加入1个人
//n*f(m-1,n)是m-1个人排成n种名次,新加入的人与他们之中的任意一个名次相同;
//n*f(m-1,n-1)是m-1个人排成n-1种名次,新加入的人不与任何一种名次相同,共有n种情况
答案为sum(f(m,i)),i=[1,m]
*/

参考知乎:n个人排名,允许并列名次,共有多少种排名结果?

发表评论

电子邮件地址不会被公开。 必填项已用*标注