题解

115 条题解

  • 0
    @ 2013-10-18 18:48:16

    program nuclear;
    var
    j,n,m,i:integer;
    f:array[-3..50,0..5] of int64;
    ma:array[0..50] of int64;
    begin
    read(n,m);
    for i:=-3 to 0 do f[i,m-1]:=0;
    f[1,m-1]:=1;
    ma[0]:=1;
    ma[1]:=2;
    f[2,m-1]:=1;
    if m=1 then ma[n]:=1
    else for i:=1 to n do begin
    ma[i]:=ma[i-1]*2-f[i-m+1,m-1];
    f[i+2,m-1]:=ma[i];
    end;
    write(ma[n]);
    end.真正意义上第一次AC动态规划,好开心。。。

  • 0
    @ 2013-09-08 15:54:44

    靠背int64坑了2次- -

  • 0
    @ 2013-07-24 14:55:57

    测试数据 #0: Accepted, time = 0 ms, mem = 464 KiB, score = 10

    测试数据 #1: Accepted, time = 15 ms, mem = 468 KiB, score = 10

    测试数据 #2: Accepted, time = 0 ms, mem = 464 KiB, score = 10

    测试数据 #3: Accepted, time = 15 ms, mem = 468 KiB, score = 10

    测试数据 #4: Accepted, time = 0 ms, mem = 472 KiB, score = 10

    测试数据 #5: Accepted, time = 0 ms, mem = 468 KiB, score = 10

    测试数据 #6: Accepted, time = 0 ms, mem = 468 KiB, score = 10

    测试数据 #7: Accepted, time = 0 ms, mem = 468 KiB, score = 10

    测试数据 #8: Accepted, time = 0 ms, mem = 464 KiB, score = 10

    测试数据 #9: Accepted, time = 0 ms, mem = 468 KiB, score = 10

    Accepted, time = 30 ms, mem = 472 KiB, score = 100

  • 0
    @ 2013-04-17 19:16:17

    测试数据 #0: Accepted, time = 0 ms, mem = 632 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 632 KiB, score = 10
    测试数据 #2: Accepted, time = 3 ms, mem = 632 KiB, score = 10
    测试数据 #3: Accepted, time = 3 ms, mem = 632 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 632 KiB, score = 10
    测试数据 #5: Accepted, time = 3 ms, mem = 632 KiB, score = 10
    测试数据 #6: Accepted, time = 3 ms, mem = 632 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 632 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 632 KiB, score = 10
    测试数据 #9: Accepted, time = 3 ms, mem = 632 KiB, score = 10
    Accepted, time = 19 ms, mem = 632 KiB, score = 100

  • 0
    @ 2012-11-23 19:34:13

    ├ 测试数据 01:答案正确... (47ms, 404KB)

    ├ 测试数据 02:答案正确... (31ms, 404KB)

    ├ 测试数据 03:答案正确... (31ms, 404KB)

    ├ 测试数据 04:答案正确... (0ms, 404KB)

    ├ 测试数据 05:答案正确... (16ms, 404KB)

    ├ 测试数据 06:答案正确... (16ms, 404KB)

    ├ 测试数据 07:答案正确... (47ms, 408KB)

    ├ 测试数据 08:答案正确... (0ms, 404KB)

    ├ 测试数据 09:答案正确... (47ms, 404KB)

    ├ 测试数据 10:答案正确... (0ms, 404KB)

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

    Accepted / 100 / 240ms / 408KB

    我的DP是用函数写的……

  • 0
    @ 2012-11-06 20:12:50

    这道题目用基本方法当然是动规,但是如果我们换种思路去考虑就简单的多了,但是当然想到稍微有点困难了.

    只要保存不会爆炸的方案,然后每多一个坑,就求出总的放核堆的可能性(是从前面少一堆且不爆炸的可能性来.因为当前堆有两种可能,放或不放.所以f[i]:=f*2;)

    然后在减去多一个堆后会产生爆炸的方案总数.那么与该点有关,所以只有连续的当前点往前M-1个点都要放核才能爆炸.且,往前推第M个点无核.所以只能一种不放的可能性.因此f[i]:=f*2-f,初始化等等见下面把.

  • 0
    @ 2012-07-23 22:37:10

    所有用C/C++的朋友注意。。一定要用%I64d或者cout输出。。用%lld会WA。。

    思路比较简单。。用的是排除法。。用f[i]表示前i个坑所有满足条件的放法总数。。显然。。若没有额外条件。。即连续放会爆炸的限制。。放法总数为f[i]=2*f。。若有连续放置的限制。。则需从总数中扣除。。若连续放置m个雷且第i个是雷。。那么必然与其连续的前m-1个坑里也全是雷。。有且仅有这一种可能性!所以。。需要从总数中减去f*1。。

    综上。。f[i]=2*f-f。。如果用C/C++写可能会比较麻烦。。边界处理会比pascal麻烦些。。不过还是很简单的。。不再赘述。。

  • 0
    @ 2010-04-12 09:13:50

    居然因为longint而WA了一把。。

    • @ 2016-07-17 16:45:52

      我也是 用long long 或 int64

  • 0
    @ 2010-04-07 17:26:20

    var

    n,m,i,j:longint;

    f:array[0..50]of int64;

    begin

    readln(n,m);

    fillchar(f,sizeof(f),0);

    f[0]:=1; f[1]:=2;

    for i:=2 to n do

    begin

    if i

  • 0
    @ 2009-11-19 22:14:29

    好囧,第一次没用long long,第二次加了却忘了把环境改成C++,第三次才秒杀,AC率降一点

    • @ 2016-07-17 16:47:57

      23333333333333333☺☺☺☺☺☺☺☺

  • 0
    @ 2009-11-09 22:06:02

    #include

    __int64 m,n,move[51]={};

    __int64 dp(__int64 from)

    {

    __int64 i=0;

    if(move[from]!=0)return move[from];

    if(from>=m)return 1;

    for(i=0;i

  • 0
    @ 2009-11-05 22:38:11

    请复制到记事本看!

    归纳一下解法:

    (1) O(n):

    f[i]表示对于前i个位置,考虑第i个位置放置情况并满足前i个位置不出现连续的m个核物质的方案数

    对于第i个位置,只有放置和不放置核物质2种选择

    所以不考虑是否爆炸的情况,那么对于前i个位置的总情况数为2*f (放置和不放置2种)

    而对于第i个位置,放入会爆炸的情况为f(不放的话不会爆炸,因为f[i]表示不爆炸的方案数)

    我们考虑下面这种情况(O表示不放,X表示放,?表示未确定):

    ? ? . . . ? ? O X X . . . X ?

    | |

    i-m i

    即从i-m+1到i-1全部放置核电站,那么对于第i个位置,我们放入就达到有m个核物质连在一起(爆炸)的情况,所以这种情况的数量为f(注意:第i-m个位置已确定为不放,不会出现放的情况,因为考虑f时就已经过滤掉了)

    回到所求的问题,对于第i个位置,满足前i个位置不出现连续的m个核物质的方案数即为

    f[i]=2*f-f (不爆炸情况=总情况-爆炸情况)

    边界条件:f[-5]=f[-4]=f[-3]=f[-2]=0 f[0]=f[-1]=1(当i=m时,即f=f[-1]。因为0,-1

  • 0
    @ 2009-11-04 21:53:07

    膜拜大

    (__) 

      /oo\___|\__|_

      \ /     ---\

      \/    /  \  \

       \|__|\_|/  *

        ||  YY|

        ||  ||  

  • 0
    @ 2009-10-31 10:39:42

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    记忆化搜索就可以

  • 0
    @ 2009-10-28 20:53:53

    数组范围用int64额

    f[i]表示以第i个坑结尾的所有方案数

    方程:

    f[i]:=f*2-f

    f*2:=第i个坑放或不放的总数

    f:=第i-m个坑必须不放(i-m+1~i已经有m个连续的坑)所以方案数就是f

  • 0
    @ 2009-10-28 14:14:18

    范围居然那么大 怪不得AC不了

  • 0
    @ 2009-10-27 19:41:40

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    怎么可以这么水

  • 0
    @ 2009-10-22 22:53:49

    为什么我总是错啊,我的方法:总共的状态数是2^n,爆炸的状态数为(n-m+2)*(n-m+1)/2,一减就行了。哪位大牛帮我看看

  • 0
    @ 2009-10-11 17:04:27

    我拿c++写的,用long long怎么还爆,换pascal就A了

    提交了6次啊!!!

  • 0
    @ 2009-10-09 09:15:26

    原来自己想的dp是这样

    f=f;

    f:=sum(f);(0

信息

ID
1232
难度
3
分类
动态规划 点击显示
标签
(无)
递交数
2769
已通过
1345
通过率
49%
被复制
5
上传者