文档章节

序关系计数问题

m2012
 m2012
发布于 2012/05/20 16:01
字数 521
阅读 138
收藏 0

 

这题以前做过,印象还是挺深刻的。
如果我们把不同的变量看成是不同的小球,如果两个变量相等的话,那么对应的小球就在同一个箱子里(箱子们有序地排成一行)。那么,原问题就等价于:
将n个不同的小球放进若干个不同的箱子,且箱子数最多为n,最小为1,每个箱子都不为空,问有多少种方案。

设f(i, n)表示把 i 个小球放进n个有序箱子的方案数,那么转移方程为:
f(i, n) = f(i - 1, n) * n + f(i - 1, n - 1) * n
这个方程的含义是:
假设存在一个方案使得i个小球在n个箱子里面,如果我们把小球i(小球的编号从1开始)从箱子里拿出来,那么可能出现的情况是:
(1)小球i所在的箱子还有其他小球
(2)小球i所在的箱子变空了

对于情况一,转移为:
将前n-1个小球放进n个箱子,然后将小球i放进那n个箱子里的其中一个,方案数为 f(i - 1, n) * n
对于情况二, 转移为:
将前i - 1个小球放进n-1个箱子,然后将小球i放进第n个箱子,最后将第n个箱子往已有的那n-1个箱子插进去,方案数为f(i - 1, n - 1) * n

 

#include <cstdio>
#include <vector>
using namespace std;

vector< vector< int > > f;

template <class VVType, class T>
void make2DVector(VVType & a, int d, int f, const T & initValue) {
    int i, j;
    a.resize(d);
    for (i = 0; i < d; ++i) {
        a[i].resize(f);
        for (j = 0; j < f; ++j) a[i][j] = initValue;
    }
}


int dp(int i, int n) {
  if (i == 1) {
    return n == 1 ? 1 : 0;
  }
  if (f[i][n] != -1) return f[i][n];

  int & ans = f[i][n];

  ans = (dp(i - 1, n) + dp(i - 1, n - 1)) * n;
  return ans;
}

int main() {
  int k;
  scanf("%d", &k);
  make2DVector(f, k + 1, k + 1, -1);

  int i, j;
  for (i = 1; i <= k; ++i)
    for (j = 1; j <= i; ++j)
      dp(i, j);
  int sum = 0;
  for (j = 1; j <= k; ++j)
    sum += dp(k, j);
  printf("%d\n", sum);
  return 0;
}


© 著作权归作者所有

共有 人打赏支持
m2012
粉丝 16
博文 129
码字总数 52548
作品 0
广州
程序员
私信 提问
netty4.x ByteBuf 基本机制及其骨架实现

概述 netty 是一个 NIO 框架,在 JDK API 已提供相对直接的 NIO Library 的情况下,几乎很少的软件系统会直接用 NIO 进行编程,也很少有开发者会直接使用 NIO 技术开发网络相关的程序。因为 ...

beanlam
2017/07/07
0
0
next_permutation(全排列算法)

STL提供了两个用来计算排列组合关系的算法,分别是nextpermutation和prevpermutation。首先我们必须了解什么是“下一个”排列组合,什么是“前一个”排列组合。考虑三个字符所组成的序列{a,...

angel_kitty
2017/02/12
0
0
【分享】使用limma、Glimma和edgeR,RNA-seq数据分析易如反掌

原文来自这里,略编辑 摘要 简单且高效地分析RNA测序数据的能力是Bioconductor的核心优势。 RNA-seq分析通常从基因水平的序列计数开始,涉及到数据预处理,探索性数据分析,差异表达检验以及...

王诗翔
01/14
0
0
图解JavaScript算法排序

一、冒泡排序 算法介绍: 比较相邻的两个元素,如果前一个比后一个大,则交换位置。 第一轮把最大的元素放到了最后面。 由于每次排序最后一个都是最大的,所以之后按照步骤1排序最后一个元素不...

大翰仔仔
02/19
0
0
数据结构-二叉树基础题目小结(遍历,求节点数目等等)

给定一个前序序列数组构造一个二叉树 思路:首先序列中要有给定的非法值,也就是二叉树中对应的空节点;对于构造一个二叉树可以使用递归的思想:先构造当前节点,再构造左子树,再右子树,直...

sssssuuuuu666
2017/12/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

[Flowable]6.4.1五个war包部署

直接放tomcat http://localhost:8080/flowable-task http://localhost:8080/flowable-modeler http://localhost:8080/flowable-idm http://localhost:8080/flowable-admin http://localhost:......

Danni3
36分钟前
3
0
扩展spring cache 支持缓存多租户及其自动过期

spring cache 的概念 Spring 支持基于注释(annotation)的缓存(cache)技术,它本质上不是一个具体的缓存实现方案(例如 EHCache 或者 OSCache),而是一个对缓存使用的抽象,通过在既有代...

冷冷gg
41分钟前
3
0
Kafka连接器深度解读之转换器和序列化释疑

Kafka连接器是Apache Kafka®的一部分,提供数据存储与Kafka之间的流式集成。对于数据工程师来说,只需要使用JSON格式配置文件即可。目前已经有很多数据存储的连接器,仅举几例来说,包括JDB...

李玉珏
47分钟前
2
0
二进制取反

取反,是Java使用补码来表示二进制数,在补码表示中,最高位为符号位,正数的符号位为0,负数为1。 概念 编辑 补码的规定如下: 对正数来说,最高位为0,其余各位代表数值本身(以二进制表示)...

天王盖地虎626
今天
7
0
OSChina 周一乱弹 —— 可乐进化史

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @-冰冰棒- :#今日歌曲推荐# 分享Radiohead的单曲《Creep》 《Creep》- Radiohead 手机党少年们想听歌,请使劲儿戳(这里) @EdmondFrank :刚...

小小编辑
今天
1K
18

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部