C/C++教程

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

本文主要是介绍集合划分讲解-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的这道题:

传送门

  • 集合划分
    • 登上火星
      • 题目描述
      • 输入描述
      • 输出描述
      • 样例一
        • 输入
        • 输出
  • 题目分析
  • AC代码


登上火星

传送门

时间限制: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

这篇关于集合划分讲解-And-2021年ACM竞赛班训练(九)2021.5.20-问题 E: 登上火星-题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!