You've successfully subscribed to ムえのBLOG
Great! Next, complete checkout for full access to ムえのBLOG
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
离散复习专题「放球问题」 与 DP

离散复习专题「放球问题」 与 DP

. 3 min read

问题:$n$个球,放到$m$个盒子里$(n≥m)$,主要有下列八种情况:

$n$个球是否有区别 $m$个盒子是否有区别 是否允许空盒
1 $F$ $F$ $F$
2 $F$ $F$ $T$
3 $F$ $T$ $F$
4 $F$ $T$ $T$
5 $T$ $F$ $F$
6 $T$ $F$ $T$
7 $T$ $T$ $F$
8 $T$ $T$ $T$

球相同,盒子相同,不允许空盒

要保证盒子大小非严格递减。每次把当前所有盒子里的球都$+1$;或者新增一个盒子,里面放一个球。
$$
f[n][m] = f[n-1][m-1]+f[n-m][m]
$$
另外,也可以从允许空盒的方案 $g$ 推出:
$$
f[n][m]=g[n-m][m]
$$

球相同,盒子相同,允许空盒

要保证盒子大小非严格递减。每次把当前所有盒子里的球都$+1$;或者新增一个盒子,里面不放球。
$$
g[n][m] = g[n][m-1]+g[n-m][m]
$$
另外,也可以从允许无空盒的方案 $g$ 推出:
$$
g[n][m] = \sum_{i=1}^{m}f[n][i]
$$

球相同,盒子不同,不允许空盒

插板法,总共$n-1$个间隔,插$m-1$个板子
$$
C_{n-1}^{m-1}
$$

球相同,盒子不同,允许空盒

可以看作,先在最后添上$m$个球,总共$n+m$个球,往里插$m-1$个板子,然后从这$m$部分中每部分拿掉一个球,就变成了这种情况
$$
C_{n-1}^{n+m-1}= \sum_{i=1}^{m}C^{i-1}_{n-1}
$$

球不同,盒子相同,不允许空盒

第二类斯特林数 $String$

考虑第$n$个球

  • 若前$n-1$个球形成了$m-1$个集合,那么第$n$个球必须新开一个集合。因为盒子没有顺序(或者说一开始已经固定了顺序),所以不用乘$n-m+1$
  • 若前$n-1$个球已经形成了$m$个集合,那第$n$个球可以插到其中任意一个中。因为第$n$个球是独一无二的,所以要乘$m$

球不同,盒子相同,允许空盒

答案就是

球不同,盒子不同,不允许空盒

答案就是

因为情况5中的每一种方案,任意两个集合交换后形成的方案一定与本身不同(若球都一样的话就不一定了,详见下文)

球不同,盒子不同,允许空盒

$$
m^n
$$



本站总访问量 正在加载今日诗词....