请问一道与集合划分有关的动态规划问题。。 - 编程论坛

#2

rjsp2018-11-21 10:49

(1 . 1)
(2 . 2)
(3 . 5)
(4 . 14)
(5 . 46)
(6 . 166)
(7 . 652)
(8 . 2780)
(9 . 12644)
(10 . 61136)
(11 . 312676)
(12 . 1680592)
(13 . 9467680)
(14 . 55704104)
(15 . 341185496)
(16 . 2170853456)
(17 . 14314313872)
(18 . 97620050080)
(19 . 687418278544)
(20 . 4989946902176)

公式是 f(n) = f(n-1)
            + f(n-2) * (n-1)
            + f(n-3) * (n-1)*(n-2)/2

------------------------------------------------------

f(0) = 1
f(1) = 1
f(2) = 2
安排第n颗糖时，可以此糖单独放一堆。那么有 f(n-1)*1 种
               可以从前n-1颗糖中拎出一颗糖，与之一堆单独放一堆。那么有 f(n-2) * (n-1)
               可以从前n-1颗糖中拎出两颗糖，与之一堆单独放一堆。那么有 f(n-3) * (n-1)*(n-2)/2

[此贴子已经被作者于2018-11-21 13:07编辑过]

#3

RKNO2018-11-21 11:12

回复 2楼 rjsp

抱歉能说明一下那个递推式的思路吗，我不是很理解？
而且运行结果好像不对。
比如4颗糖分堆：

先写出3颗糖的：(5种)
{1}{2}{3}
{12}{3}
{13}{2}
{1}{23}
{123}
1、在3颗糖的基础上另分一堆，有下面5种情况（和3颗糖分堆的总次数相同）
{1}{2}{3}{4}
{12}{3}{4}
{13}{2}{4}
{1}{23}{4}
{123}{4}
2、在3颗糖的基础上将第4颗插入小于3的堆里面，有下面9种情况
{14}{2}{3}
{1}{24}{3}
{1}{2}{34}
{124}{3}
{12}{34}
{134}{2}
{13}{24}
{14}{23}
{1}{234}
加起来一共14种情况。而程序运行结果是13。。

#4

rjsp2018-11-21 11:21

看来我计算错了

#5

rjsp2018-11-21 13:23

分析见2楼

程序代码：

#include <iostream>
using namespace std;

int main( void )
{
    unsigned long long f[21] = { 1, 1 };
    for( size_t i=2; i!=21; ++i )
        f[i] = f[i-1]*1 + f[i-2]*(i-1) + f[i-3]*((i-1)*(i-2)/2);

    for( size_t n; cin>>n; )
        cout << f[n] << '\n';
}

#6

RKNO2018-11-21 17:11

好牛！

我怎么就想不到。谢谢了！！

有一个小小的问题，输入的范围包括了0，但0的输出结果应该是0而不是1，输入时加个判断就行了。再次感谢。

#7

rjsp2018-11-22 08:33

但0的输出结果应该是0而不是1

我觉得0颗糖果时，应当是1种分堆方案。（一种方案：分成0堆）
而且在公式上，已知f(2)、f(1)也可以推导出f(0)==1

#8

RKNO2018-11-22 18:18

回复 7楼 rjsp

嗯，反正要么是0要么是1。也不用太过纠结。但我个人更偏向于0，因为要符合“每堆至少1颗糖”这个条件。