题目不难，但要仔细

初始化：f[n][v]=v

方程为:f[i][j]=max(f[j-1],f[j],f[j+1])+j

注意：当该速度不满足条件时则f[i][j]=0

(以前的“题解”被删了，吸取上次的教训，重新发了题解^_^)

景天从上往下走，怪的速度是从下往上给的= = 坑坑坑！

DP是什么意思吗？

初速度为

题目数据应该有N层楼的速度吧?!每一层楼都应该保证不被踩死又不踩死妖啊!!

景天从2楼到一楼的速度应该要保证在一楼不被踩死又不踩死妖吧...?

N楼下N-1楼的速度难道不是应该要保证在N-1楼不被踩死又不踩死妖吗?怎么按题目意思是N楼下N-1楼的速度保证在N楼不被踩死又不踩死妖...?

囧，WA了几次……

最后还是A了

#include

#include

using namespace std ;

const int maxspeed = 220 ;

const double oo = 9999999 ;

int n, v, k, speed[102] ;

double f[102][maxspeed + 2], ans ;

void Init ()

{

scanf ( "%d%d%d", &n, &v, &k ) ;

for ( int i = 2 ; i ?= ( f[i + 1][j + 1] * ( n - 1 ) + j ) / double ( n - 1 ) ;

} ;

for ( int i = 0 ; i ?= f[2][i] ;

if ( ans == - oo ) ans = - 1 ;

} ;

bool SpChk ()

{

if ( v - speed[n] > k ) return ( true ) ;

if ( v < speed[n] ) return ( true ) ;

return ( false ) ;

} ;

void Output ()

{

if ( ans == - 1 )

printf ( "REN JIU SHI BU NENG REN CI!\n" ) ;

else

printf ( "%0.2lf\n", ans ) ;

} ;

int main ()

{

Init () ;

if ( SpChk () )

{

ans = - 1 ;

Output () ;

}

else

{

Dp () ;

Output () ;

} ;

return ( 0 ) ;

} ;

初学者写的程序。。丑陋啊。。

第1次因为！和! 90分。。。

、、真囧，不知道为什么100*100竟然第一次评测超时6个点。

• =WA了N次才发现原来求的是每次【下塔时】的速度和= =不幸算成了每层的速度和= =
  

AC率下降2= =

水题还交了3遍。。。。。

交了3次 一次记忆化一次循环递推 还有一次少了一个等号。。。。。

难道递归的效率已经地下到这种程度了？？3个点超时。。。。。。

（刚开始以为是没有碰到Puppy的原因。。。。后来碰到了照样超时。。。。）

本来是拿小号做实验的 等正式交的时候竟然忘换号了。。。。。。我绝对不是抄袭~~~~幸好没封号。。。。（因为我动了点小手脚）

通样交了2次。。

第一次。!问题+for j:=s[i]+1 to s[i]+k 40

第二次。看题解 。。。。终于AC

现在越来越对水题恐惧了~~~~~~

交了三次……

第一次没注意万恶的浮点数

第二次连着while(1)交上去了

第三次终于AC了

PS：

如果本题改成求锁妖塔四层走法，那难度就不是1了……

镇妖剑是在塔底被景天拔走的，不是塔顶！

题目中“景天刚拿到镇妖剑”还“下塔”是怎么回事？

顶层的是魔剑，楼哥早就把拔掉了。

DP啊

/color=red/??

一元DP；唉，数组忘了清空，还得我交了4次，另外注意第2行的顺序。

现在觉得二维的还是好些，虽然占空间。

var

ok:boolean;

a1,a2,a3,a4,n,v1,k,mm:longint;

v:array[1..100] of longint;

f,f1,tf,tf1:array[-400..400] of longint;

ca:real;

function max(b1,b2:longint):longint;

begin

if b1>b2 then max:=b1 else max:=b2;

end;

begin

readln(n,v1,k);

for a1:=1 to n-1 do read(v[a1]);

tf[v1]:=1;

for a1:=n-1 downto 1 do

begin

fillchar(f1,sizeof(f1),0);

fillchar(tf1,sizeof(tf1),0);

ok:=false;

for a2:=v[a1]+k downto v[a1] do

if tf[a2]=1 then

begin

ok:=true;

f1[a2+1]:=max(f1[a2+1],f[a2]+a2);

f1[a2]:=max(f1[a2],f[a2]+a2);

f1[a2-1]:=max(f1[a2-1],f[a2]+a2);

tf1[a2+1]:=1; tf1[a2-1]:=1; tf1[a2]:=1;

end;

if ok=false then

begin

writeln('REN JIU SHI BU NENG REN CI!');

halt;

end

else

begin

for a2:=v[a1]-1 to v[a1]+k+1 do f[a2]:=f1[a2];

tf:=tf1;

end;

end;

for a1:=v[1]+k downto v[1] do if f[a1]>mm then mm:=f[a1];

ca:=mm/(n-1);

writeln(ca:0:2);

end.

我说怎么一直WA嘛。原来是从上到下跑，速度数据是从下到上给的……

魔剑可是我先发现的

DP

f=max(f,f,f)

如对本题有疑问可以参看我的题解：http://xujieqi.blog.hexun.com/35722312_d.html

居然没想到景天除了谈钱的时候话里有感叹号,,发牢骚也会有..........害他过来3次锁妖塔...