集合划分讲解-And-2021年ACM竞赛班训练(九)2021.5.20-问题 E: 登上火星-题解

集合划分

集合划分,把 n n n个数分成 k k k个集合,不能包含空集,所有的划分数量记为斯大林数,用 S ( n , k ) S(n,k) S(n,k)表示。

目前斯大林数没有直接的公式,但是有递推公式。

S(n,k)=S(n-1,k-1)+k*S(n-1,k)

终止条件:S(n,n)=1(n数分n份)、S(n,1)=1(n数分1份)
可以理解为:

把n个数分成k份

  • 如果前面n-1个数分成了k-1份,那么这个第n个数必须独自一个集合,方法数=前面n-1个数分成k-1份的方法数。
  • 如果前面n-1个数已经分成了k份,那么这个第n个数可以放到这分好的k个集合中的任意一个,所以乘以k。

注意,这种分配方式中,被分配的苹果是不同的,盛放苹果的篮子是相同的。

那么对于我校OJ的这道题:

传送门


登上火星

传送门

时间限制:1秒
空间限制:128M


题目描述

  • 2021年5月15日,中国探测器登上火星!这是一个值得纪念的日子。

  • 2137年,中国CNSA研制成功了可以登上火星的载人飞船。

n个人乘坐k个飞船去火星,每个飞船视为相同,问有多少中乘坐方法?

注意,如果有空的飞船,CNSA是不会点火的。所以请保证每艘飞船都有人。


输入描述

给你两个数 n n n和 k k k,通过空格隔开,保证 n ≥ k n\geq k n≥k,代表 n n n个人乘坐 k k k艘飞船。
科技在进步,当年最多承载 25 25 25人去火星,总共有 25 25 25艘飞船。( 0 < n ≤ 25 , 0 < k ≤ n 0<n\leq 25,0<k\leq n 0<n≤25,0<k≤n)


输出描述

请输出有多少种不同的乘坐方法


样例一

输入

4 2

输出

7

题目分析

直接参考前面的递推公式即可。


AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll S[30][30]={0};
ll getS(int n,int k)
{
    if(S[n][k])return S[n][k];
    if(n==k||k==1)return S[n][k]=1;
    return S[n][k]=getS(n-1,k-1)+k*getS(n-1,k);
}
int main()
{
    int n,k;
    cin>>n>>k;
    cout<<getS(n,k)<<endl;
    return 0;
}

原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/117063879

上一篇:小题狂练目录


下一篇:ACM比赛完了后怎么办