【递归与递推】集合的划分

【递归与递推】集合的划分

题目描述

设s是一个具有n个元素的集合,s={a1,a2,……,an},现将s划分成k个满足下列条件的子集合s1,s2,……,sk,且满足:
(1)si≠∅
(2)si∩sj=∅
(3)s1∪s2∪s3∪...∪sk=s
则称s1,s2,...,sk是集合s的一个划分。它相当于把s集合中的n个元素a1,a2,...,an放入k个(0<k≤n<30)无标号的盒子中,使得没有一个盒子为空。请你确定n个元素a1,a2,...,an放入k个无标号盒子中去的划分数s(n,k)。

输入

两个整数n和k

输出

一个整数,划分数s(n,k)。

样例输入

4 3分析:第二类斯特林数;(球盒模型的一种)代码:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
const int maxn=1e4+10;
const int dis[][2]={0,1,-1,0,0,-1,1,0};
using namespace std;
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p%mod;p=p*p%mod;q>>=1;}return f;}
int dfs(int x,int y)
{
    if(x<y||y==0)return 0;
    else if(y==1||x==y)return 1;
    else return dfs(x-1,y-1)+y*dfs(x-1,y);
}
int main()
{
    int i,j,m,n,k,t;
    scanf("%d%d",&n,&m);
    cout<<dfs(n,m)<<endl;
    //system("pause");
    return 0;
}
 
时间: 07-05

【递归与递推】集合的划分的相关文章

【递归与递推】计数器

问题 F: [递归与递推]计数器 题目描述 一本书的页数为N,页码从1开始编起,请你求出全部页码中,用了多少个0,1,2,…,9.其中—个页码不含多余的0,如N=1234时第5页不是0005,只是5. 输入 一个正整数N(N≤109),表示总的页码. 输出 共十行:第k行为数字k-1的个数. 样例输入 11 样例输出 1 4 1 1 1 1 1 1 1 1 #include <iostream> #include <cstring> #include <cstdio>

【递归与递推】电话号码

问题 L: [递归与递推]电话号码 题目描述 电话机上每一个数字下面都写了若干个英文字母.分布如下:       1-abc       2-def       3-ghi       4-ikl       5-mn       6-opq       7-rst       8-uvw       9-xyz  现在给定一个单词表和一串数字密码,请你用单词表中的单词翻译这个密码. 输入 第一行为一个正整数N表示单词表中单词的个数(N≤100): 第二行为一个长度不超过100的数字串,表示密码

递归,递推,记忆化搜索,空间优化(数字三角形)

题目链接:http://poj.org/problem?id=1163 1.递归思想:第一层到最底层的最优路径可以分解为:第一层到第二层来,再加上第二层的最优路径 状态: Time Limit Exceeded #include <algorithm> #include <stdio.h> #define MAX 101 using namespace std; int maps[MAX][MAX]; int n; int Sum(int i,int j) { if(i==n) r

【递归与递推】诸侯安置

[递归与递推]诸侯安置 题目描述 很久以前,有一个强大的帝国,它的国土成正方形状,如图2—2所示. 这个国家有若干诸侯.由于这些诸侯都曾立下赫赫战功,国王准备给他们每人一块封地(正方形中的一格).但是,这些诸侯又非常好战,当两个诸侯位于同一行或同一列时,他们就会开战.如下图2—3为n=3时的国土,阴影部分表示诸侯所处的位置.前两幅图中的诸侯可以互相攻击,第三幅则不可以. 国王自然不愿意看到他的诸侯们互相开战,致使国家动荡不安.  因此,他希望通过合理的安排诸侯所处的位置,使他们两两之间都不能攻击

【递归与递推】排序集合

[递归与递推]排序集合 题目描述 对于集合N={1,2,…,n}的子集,定义一个称之为“小于”的关系:设S1={X1,X2,…,Xi},(X1<X2<…<Xi),S2={Y1, Y2, …,Yj},(Y1<Y2<…<Yj),如果存在一个k,(0≤k≤min(i,j)),使得X1=Y1,…,Xk=Yk,且k=i或X(k+1)<Y(k+1),则称S1“小于”S2.你的任务是,对于任意的n(n≤31)及k(k<2n),求出第k小的子集. 输入 仅一行,包含两个用空

【递归与递推】编码

[递归与递推]编码 题目描述 编码工作常被运用于密文或压缩传输.这里我们用一种最简单的编码方式进行编码:把一些有规律的单词编成数宇. 字母表中共有26个字母{a,b,…,z},这些特殊的单词长度不超过6且字母按升序排列.把所有这样的单词放在一起,按字典顺序排列,一个单词的编码就对应着它在字典中的位置. 例如:    a→1    b→2    z→26    ab→27    ac→28 你的任务就是对于所给的单词,求出它的编码. 输入 仅一行,被编码的单词. 输出 仅一行,对应的编码.如果单词

【递归与递推】遍历问题

[递归与递推]遍历问题 题目描述 我们都很熟悉二叉树的前序.中序.后序遍历,在数据结构中常提出这样的问题:已知一棵二叉树的前序和中序遍历,求它的后序遍历,相应的,已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历.然而给定一棵二叉树的前序和后序遍历,你却不能确定其中序遍历序列,考虑如下图中的几棵二叉树: a                      a                         a                        a /               

数字三角形——递归、递推、记忆化搜索

数字三角形 描述: 有一个由非负整数组成的三角形,第一行只有一个数,除了最下行之外没个数的左下方和右下方各有一个数. 问题: 从第一行的数开始,每次可以往左下或右下走一格,直到走到最下行,把沿途经过的数全部加起来.如何走才能使得这个和尽量大? 分析: 不难看出此题是一个动态的决策问题:每次有两种选择--左下或右下.如果用回溯法求出所有的可能的路线,就可以从中选出最优的路线.但和往常一样,回溯法的效率太低:一个n层数字三角形的完整路线有2^n条,当n很大时回溯法的速度将让人无法忍受.因此本题讨论用

nyist 17 -----纯递归纯递推--超时

#include <iostream>#include<stdio.h>#include<string.h>using namespace std;char a[10002];int b[10002];int n,ans;int f(int x){ int i,t; for(i=0;i<=x-1;i++) { t=f(i); if(a[i]<a[x] && b[x]<t+1) b[x]=t+1; } return b[x];} int