讨论 / AC100题留念——L.Lawliet
L.Lawliet 2010-11-17 01:01:00
点我顶贴 收藏 删除
终于[color=green]AC[/color][color=red]100[/color]题了 希望在今年NOIp上能拿一等奖

附此题题解:

开始写的是递归版DP 结果堆栈溢出了。。

只好又写了循环版 居然诡异的总是WA70 改了大半天才发现少加了括号= =!

再次栽在自己粗心大意上...

题目:SY学语文

状态:[color=green] Accepted [/color]

测评机: Xeost[5]

得分: 100分

提交日期: 2010-7-1 12:49:00

有效耗时: 2265毫秒

测试结果1:[color=green] 通过本测试点|有效耗时172ms [/color]

测试结果2:[color=green] 通过本测试点|有效耗时62ms [/color]

测试结果3:[color=green] 通过本测试点|有效耗时63ms [/color]

测试结果4:[color=green] 通过本测试点|有效耗时62ms [/color]

测试结果5:[color=green] 通过本测试点|有效耗时172ms [/color]

测试结果6:[color=green] 通过本测试点|有效耗时172ms [/color]

测试结果7:[color=green] 通过本测试点|有效耗时172ms [/color]

测试结果8:[color=green] 通过本测试点|有效耗时187ms [/color]

测试结果9:[color=green] 通过本测试点|有效耗时453ms [/color]

测试结果10:[color=green] 通过本测试点|有效耗时750ms [/color]

program SYC{循环版};

const maxn=1000;

var a:array[0..maxn,0..maxn]of longint;//记录地图

f:array[0..maxn,0..maxn]of longint;//记录值

i,j,k,m,n,max:longint;

{main}

begin

max:=-1;

readln(n,m);

for i:=1 to n do

for j:=1 to m do

read(a[i,j]);

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

f[1,1]:=a[1,1];

for i:=2 to n do

for j:=2 to m do

begin

if a[i,j]=-1 then continue;//该位置为石子..跳过不计算

if (f[i-1,j-2]=0)and(f[i-2,j-1]=0)then continue;//如果我对该位置进行计算 那么 首先要确认其可能性 一定有一个点能达到该位置 否则 jump..

if f[i-1,j-2]>f[i-2,j-1] then f[i,j]:=f[i-1,j-2]+a[i,j]

else f[i,j]:=f[i-2,j-1]+a[i,j];//选取一个较大的点作为该点的前一位置 实现最优

if [color=red]([/color](i=n)or(j=m)[color=red]){就是这对括号= =!}[/color]and(f[i,j]>max)then max:=f[i,j];//如果达到了边界 对max进行重新处理

end;

if max=-1 then writeln('cannot arrive.')else writeln(max);//如果max没被赋值过 那一定是不存在使题目出解的情况 输出‘cannot arrve.’

end.

[color=pink]在此感谢renqing及RQNOJ的工作人员 他们的努力让我们有了一个好的做题平台 谢谢啦!![/color]

#1 renqing@2010-07-01 00:55:00
回复 删除
题解应附有解题的思路,而不仅仅有代码
#2 L.Lawliet@2010-07-01 01:02:00
回复 删除
回复 沙发renqing 的帖子

我修改了帖子...

#3 L.Lawliet@2010-11-17 01:01:00
回复 删除
顶上去~
查看更多回复
提交回复