题解

245 条题解

  • 0
    @ 2007-07-26 11:47:05

    program p1117;

    var i,j,n,k:integer;

    f:array [-5..200,0..6] of qword;

    begin

    readln(n,k);

    f[1,1]:=1;

    for i:=1 to n do

    for j:=1 to k do

    if not ((i=1) and (j=1)) then

    f:=f+f;

    writeln(f[n,k]);

    end.

    ---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|-

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    递推式f(n,k)=f(n-1,k-1)+f(n-k,k)。

    上面的递推式比较好理解,为了拆出不同的解,我们只要拆分出的数排序后两两不同即可。每种拆分方案中,排序后最小的数为e,按照e的不同,我们可以把拆分方案分成2类:

    e=1,我们把1除去,则剩余部分正好是n-1拆分成k-1部分,一共有f(n-1,k-1)个;

    e>1,因为e是最小的数,所以所有的数都>1,我们把所有的数-1,则正好是n-k拆分成k部分,一共有f(n-k,k)个。

    根据加法原理,得出以上递推式。

    知道递推式后,就比较简单了,我们用动态规划的方法(如果直接递归,会有很多重复运算)。

  • 0
    @ 2007-07-23 15:54:47

    920 ms 呵呵

  • 0
    @ 2007-07-16 16:50:01

    一种莫名的冲动

    交表

    虽然较长

    但更容易想明白

    (第一次用DP做 竟然只有20分 太失望……)

    交表 就是judge k

  • 0
    @ 2007-06-02 20:06:35

    楼下的

    g

    是不是这出问题了

  • 0
    @ 2007-05-20 12:54:30

    DP水平才差,写了个普通搜索

  • 0
    @ 2007-05-18 11:40:18

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 556ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:556ms

    不剪枝的深度搜索就能AC......

  • 0
    @ 2007-04-05 17:32:44

    上课时想出一种神奇的方法:)

  • 0
    @ 2007-03-30 00:12:39

    search + cut treenode !

    0 seonds!

  • 0
    @ 2007-03-27 19:09:01

    总觉得有点错误,在研究了程序半天,觉得找不到错误。抱着试试的心态,结果直接AC。。。

    PS:如果优化的好:前面的数〈=后面的数。以7,3为例,1+1+5合法,1+5+1不合法

    0msAC

  • 0
    @ 2006-12-11 16:00:08

    记忆化搜索

    利用Ferrers那个旋转, 把数n分成k份的总拆分数,就等同于把n进行拆分,最大一份为k的所有拆分数

  • 0
    @ 2006-12-11 11:19:22

    搜索都ac。。。无奈

  • 0
    @ 2006-12-02 22:28:51

    搜索+剪枝+Vivid Puppy=AC

  • 0
    @ 2006-11-16 09:19:27

    谈下我对这个公式的理解:

    f[i][j]=f[j]+f[j-1];

    f[i][j]就是i的j划分。

    若划分出的一些数中有1,则把他拿掉,剩下的部分划分数就是f[j-1]。

    若没有,就想像为每个部分都是一个柱子,都把最下面一层拿掉,上面剩下的划分数就是f[j]。

    由于是在分类讨论,所以最后加起来^-^

  • 0
    @ 2006-11-15 19:22:07

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 25ms

    ├ 测试数据 05:答案正确... 759ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:784ms

    穷举!!!非DP只递归

  • 0
    @ 2008-09-27 21:47:52

    同楼上的大牛

  • 0
    @ 2006-11-09 23:27:08

    dfs.......

  • 0
    @ 2006-10-30 15:51:48

    16行就过了.

    opt[n,k]=sigma f[n-k,t],1

  • 0
    @ 2006-10-29 03:07:41

    这题正解是DP.但我对DP没什么感觉,况且这题也是弱数据,于是就搜....

    数据很小,随便卡卡条件就可以过.

  • 0
    @ 2006-10-07 15:31:02

    可恶啊,我用dfs只能过前四个,5555555

    只好用DP...

  • 0
    @ 2006-10-07 12:35:11

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

信息

ID
1117
难度
3
分类
动态规划 点击显示
标签
递交数
6168
已通过
3140
通过率
51%
被复制
14
上传者