题解 - Vijos

0

yjl3567618 LV 8 @ 2009-10-25 10:56:10

完全爆搜，没想到竟过了

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var i,j,m,n,r,c1,ans:longint;

f,k:array[0..500,0..500] of longint;

c:array[0..500,0..500] of boolean;

procedure try(a,b:longint);

begin

if (k[a,b]>k[a-1,b]) and (not c[a-1,b]) and (f[a,b]+1>f[a-1,b]) and (a-1>0) then begin f[a-1,b]:=f[a,b]+1;c[a-1,b]:=true;try(a-1,b);c[a-1,b]:=false;end;

if (k[a,b]>k[a+1,b]) and (not c[a+1,b]) and (f[a,b]+1>f[a+1,b]) and (a+1k[a,b-1]) and(not c[a,b-1]) and (f[a,b]+1>f[a,b-1]) and (b-1>0) then begin f[a,b-1]:=f[a,b]+1;c[a,b-1]:=true;try(a,b-1);c[a,b-1]:=false;end;

if (k[a,b]>k[a,b+1]) and(not c[a,b+1]) and (f[a,b]+1>f[a,b+1]) and (b+1ans then ans:=f;

writeln(ans);

end.

0

gsrq LV 10 @ 2009-10-23 18:52:44

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

400次提交后……

NOIP RP++

0

一路向北 LV 8 @ 2009-10-23 17:21:11

先前将m写成n,只能过八个点（数据真的很弱啊），害得我苦苦寻觅了几个小时。。

也痛苦了几个小时！

0

qiaomingda LV 8 @ 2009-10-11 19:54:26

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

记忆化搜索,第一次局部变量未定义WA了,第二次就AC了

0

hssyxxedu LV 7 @ 2009-10-08 09:07:41

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var

h,max:array[0..500,0..500] of longint;

max1,i,j,r,c:longint;

function try(i,j:longint):longint;

var now:longint;

begin

if max-1

then try:=max

else begin

try:=0;

if (i-1>=1)and(h>h)and(try(i-1,j)+1>try) then try:=try(i-1,j)+1;

if (i+1h)and(try(i+1,j)+1>try) then try:=try(i+1,j)+1;

if (j+1h)and(try(i,j+1)+1>try) then try:=try(i,j+1)+1;

if (j-1>=1)and(h>h)and(try(i,j-1)+1>try) then try:=try(i,j-1)+1;

if try=0 then max:=1

else max:=try;

end;

end;

begin

readln(r,c);

for i:=1 to r do

for j:=1 to c do

begin

read(h);

max:=-1;

end;

for i:=1 to r do

for j:=1 to c do

begin

try(i,j);

if max>max1 then max1:=max;

end;

writeln(max1);

end.

0

yujiakun1995 LV 7 @ 2009-10-07 22:11:31

一开始没搞清楚 x1

0

gallenvara LV 7 @ 2009-10-07 13:56:47

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

PS：记忆化搜索=DP

0

马天翼 LV 8 @ 2009-10-02 16:13:59

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program ma;

var

a,f:array[0..1000,0..1000] of longint;

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

procedure hs(i,j,k:longint);

begin

if k>maxs then

maxs:=k;

if f>0 then

begin

if k+f-1>maxs then

begin

maxs:=k+f-1;

exit;

end;

end

else

begin

if (a>0)and(a0)and(a0)and(a0)and(amax then

max:=maxs;

end;

write(max);

end.

记忆化搜索就是不一样

0

让爷。 LV 8 @ 2009-09-23 12:57:15

DP 搜索都能A

var i,j,n,m,k,l,o,max:longint;

a,b:array[0..1000,0..1000] of longint;

procedure try(x,y,p:longint);

var i,j:longint;

begin

b[x,y]:=p;

if (a[x+1,y]b[x+1,y]) then try(x+1,y,p+1);

if (a[x,y+1]b[x,y+1]) then try(x,y+1,p+1);

if (a[x-1,y]b[x-1,y]) then try(x-1,y,p+1);

if (a[x,y-1]b[x,y-1]) then try(x,y-1,p+1);

end;

begin

max:=0;

read(n,m);

for i:=0 to 501 do

for j:=0 to 501 do

a:=maxlongint;

for i:=1 to n do

begin

for j:=1 to m do

read(a);

readln;

end;

for i:=1 to n do

for j:=1 to m do

if b=0 then try(i,j,1);

for i:=1 to n do

for j:=1 to m do

if b>max then max:=b;

writeln(max);

end.

0

fp_gzc LV 10 @ 2009-09-22 23:08:19

25w的排序要秒杀，不行吧

0

library LV 8 @ 2009-09-20 23:46:27

强烈同意楼下。。。。为什么空间要开那么大才能过。。。。

堆排居然无法秒杀。。。囧。。

0

song19931218 LV 9 @ 2009-09-19 13:04:09

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program p1011;

type

node=record

x,y,h:longint;

end;

shuzu=array[1..500000] of node;

var

b,f:array[0..1000,0..1000] of longint;

a:shuzu;

n,m,i,j,k,xx,yy,hh,max,opt:longint;

procedure q(var a:shuzu; l,r:longint);

var

tp:node; i,j,x:longint;

begin

i:=l; j:=r;

x:=a[(l+r) div 2].h;

repeat

while a[i].hx do dec(j);

if ij;

if lopt) then opt:=f+1;

i:=xx+1;

if (hh>b) and (f+1>opt) then opt:=f+1;

i:=xx; j:=yy-1;

if (hh>b) and (f+1>opt) then opt:=f+1;

j:=yy+1;

if (hh>b) and (f+1>opt) then opt:=f+1;

f[xx,yy]:=opt;

if opt>max then max:=opt;

end;

write(max);

end.

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

编译通过...

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

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

├ 测试数据 03：运行超时|无输出...

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

├ 测试数据 05：运行超时|无输出...

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

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

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

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

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

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

Unaccepted 有效得分：80 有效耗时：56ms

program p1011;

type

node=record

x,y,h:longint;

end;

shuzu=array[1..300000] of node;

var

b,f:array[0..600,0..600] of longint;

a:shuzu;

n,m,i,j,k,xx,yy,hh,max,opt:longint;

procedure q(var a:shuzu; l,r:longint);

var

tp:node; i,j,x:longint;

begin

i:=l; j:=r;

x:=a[(l+r) div 2].h;

repeat

while a[i].hx do dec(j);

if ij;

if lopt) then opt:=f+1;

i:=xx+1;

if (hh>b) and (f+1>opt) then opt:=f+1;

i:=xx; j:=yy-1;

if (hh>b) and (f+1>opt) then opt:=f+1;

j:=yy+1;

if (hh>b) and (f+1>opt) then opt:=f+1;

f[xx,yy]:=opt;

if opt>max then max:=opt;

end;

write(max);

end.

你能发现两次的程序有什么不同吗？？？

恭喜你答对了，就是数组范围不同。。。。。。。。。。。无语

0

strini LV 8 @ 2009-09-18 12:19:33

一个if决定了20分与9msAc的差距。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

PS: 神机赐我Rp..........

0

vasile LV 8 @ 2009-09-17 21:24:28

编译通过...

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

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

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

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

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

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

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

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

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

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

C++ 的记忆化搜索。。。。。。。。。。。

我的Oms到哪里去了呀。。。55555555555~~~

0

lishunzhi LV 9 @ 2009-09-17 20:52:25

编译通过...

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

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

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

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

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

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

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

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

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

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

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

QSORT+DP.哎.开始没判高度一样的.一直90分

0

cqyzzzl LV 8 @ 2009-09-10 00:45:08

QSORT+DP的同学

如果第9个数据202了

就把QSORT栈深限制为50 就可以过了

可怜的pascal阿。。。。。。。

就是以下程序的times

procedure qksort(l,r:longint);

var i,j,x:longint;

t:xy;

begin

inc(times);

if times>50 then exit;

i:=l; j:=r; x:=a[queue[i].x,queue[i].y];

repeat

while a[queue[i].x,queue[i].y]x do dec(j);

if ij;

if il then qksort(l,j);

dec(times);

end;

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

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

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

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

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

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

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

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

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

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

0

Spirit_Night LV 10 @ 2009-09-08 10:57:44

先根据高度排序

然后按照高度的顺序DP

可以在线性时间内完成

0ms

0

hxlong LV 10 @ 2009-10-08 18:16:00

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

排序一下然后DP

WS的SUNNY

0

zh_bin LV 8 @ 2009-09-05 17:52:07

有时候记忆化搜索比dp好用多啦！

const

xt:array[1..4] of integer=(0,0,-1,1);

yt:array[1..4] of integer=(-1,1,0,0);

var a,f:array[0..501,0..501] of longint;

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

function so(sx,sy:integer):longint;

var i,k,x,y:longint;

begin //记忆化搜索，寻找终端路径

if f[sx,sy]>0 then

exit(f[sx,sy]);

for i:=1 to 4 do

begin

x:=sx+xt[i];y:=sy+yt[i];

if (x>=1)and(x=1)and(yans then ans:=f;

end;

writeln(ans);

end.

0

prince_hao LV 10 @ 2009-09-05 11:39:59

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

简单的记忆化搜索

题解

358 条题解

清帝之惑之顺治

信息

状态

开发

支持

题解

358 条题解

清帝之惑之顺治

信息

状态

开发

支持

还没有账户？

登录