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动态规划，好开心。。。

靠背int64坑了2次- -

测试数据 #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: 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

├ 测试数据 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是用函数写的……

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

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

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

所有用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麻烦些。。不过还是很简单的。。不再赘述。。

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

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

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

#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

请复制到记事本看！

归纳一下解法：

(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

膜拜大

(__)　

　 /oo\___|\__|_

　 \　/　　　　 ---\

　 \/　　　 /　 \　 \

　　　\|__|\_|/　 *

　　　 ||　 YY|

　　　 ||　　|| 　

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

记忆化搜索就可以

数组范围用int64额

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

方程：

f[i]:=f*2-f

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

怎么可以这么水

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

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

提交了6次啊!!!

原来自己想的dp是这样

f=f;

f:=sum(f);(0