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

2023-11-15 12:11:58

集合划分

集合划分，把 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

输出

题目分析

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

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

码农公寓