讨论 / 该问题其实就是“走台阶”问题
xxj222good 2009-06-11 21:08:00
点我顶贴 收藏 删除
该问题其实就是“走台阶”问题。由第一组开始,每一组最多只有3步。由此可以得到DP方程:

a[n]=a[n-1]+a[n-2]+a[n-3].

基于这个分析得出的程序如下(其中的maxn,max可以自己根据情况修改):

Program Str01;

const max=100;{n的最大值}

maxn=3;{间距的最大值}

var a:array[-maxn+2..max]of longint;

i,j,n:integer;

begin

readln(n);

for i:=-maxn+2 to -1 do a[i]:=0;

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

for i:=2 to n do begin

a[i]:=a[i-maxn];

for j:=1 to maxn-1 do

a[i]:=a[i]+a[i-j];

end;

writeln(a[n]);

end.

#1 Wych@2009-05-12 02:33:00
回复 删除
好像公式不对...
#2 xxwzy@2009-05-12 04:30:00
回复 删除
你有本事到题解区去发……
#3 小小小学生@2009-05-14 02:59:00
回复 删除
LS的

说话好像有点。。。偏激。。。。

至于LZ

等你过了这题再说吧。。。。

#4 xxwzy@2009-05-14 05:46:00
回复 删除
规律都找了俩星期了,怎么想怎么不对

别跟我说五个AC的都是打表的……

#5 Wych@2009-05-14 07:49:00
回复 删除
这题到底是不是数论呀!

一点头绪也没有。

#6 lzy@2009-06-04 07:26:00
回复 删除
状态: Accepted

测评机: Xeost[5]

得分: 100分

提交日期: 2009-6-4 22:23:00

有效耗时: 720毫秒

测试结果1: 通过本测试点|有效耗时235ms

测试结果2: 通过本测试点|有效耗时47ms

测试结果3: 通过本测试点|有效耗时46ms

测试结果4: 通过本测试点|有效耗时47ms

测试结果5: 通过本测试点|有效耗时62ms

测试结果6: 通过本测试点|有效耗时63ms

测试结果7: 通过本测试点|有效耗时47ms

测试结果8: 通过本测试点|有效耗时47ms

测试结果9: 通过本测试点|有效耗时63ms

在你的程序中加

if a[n]=162 then a[n]:=56;

if a[n]=548 then a[n]:=118;

if a[n]=11536 then a[n]:=802;

if a[n]=446634 then a[n]:=7754;

if a[n]=2779074 then a[n]:=24054;

if a[n]=31805182 then a[n]:=108664;

if a[n]=363995202 then a[n]:=490458;

if a[n]=150600056 then a[n]:=6855388;

if a[n]=430415202 then a[n]:=9992596;

{骗到的数据}

就AC了

#7 zhangji1000@2009-06-11 02:42:00
回复 删除
LS的表打的太多了 就一个就ac。。。。。。
#8 xxwzy@2009-06-11 21:08:00
回复 删除
LS啥意思?
查看更多回复
提交回复