题解 - Vijos

0

zbh_wee LV 8 @ 2009-07-26 20:00:31

Program P1011;

var

height:array[1..500,1..500] of longint;

longest:array[1..500,1..500] of longint;

answer:longint;

r,c:integer;

Function max(a,b:longint):longint;

begin

if a

0

sanguoyanyi LV 7 @ 2009-07-25 13:30:42

还是dfs吧

0

董 LV 10 @ 2009-07-24 19:09:17

http://hi.baidu.com/%CB%D5%CC%DAsauterne/blog

0

cmcmccmm LV 7 @ 2009-07-23 13:10:25

program huaxue;

var a,f:array[-1..500,-1..500] of longint;

i,m,n,l,maxn:longint;

function max(ii,ll:longint):longint;

begin

if ii>ll then exit(ii) else exit(ll);

end;

procedure work(x,y:longint);

var j,k:longint;

begin

f[x,y]:=1;

for j:=-1 to 1 do

for k:=-1 to 1 do

begin

if ((j+k=-1) or (j+k=1)) and (a[x+j,y+k]f[x,y]) then f[x,y]:=f[x+j,y+k]+1;

end;

end;

end;

begin

fillchar(f,sizeof(f),-1);

read(m,n);

for i:=1 to m do

for l:=1 to n do

begin

read(a);

f:=0;

end;

for i:=1 to m do

for l:=1 to n do

begin

work(i,l);

if f>maxn then maxn:=f;

end;

write(maxn);

end.

编译通过...

├ 测试数据 01：答案错误...程序输出比正确答案长

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

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

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

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

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

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

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

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

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

当初把题意弄错了,把当成周围一圈都可以滑雪的,结果一直没过,后来改了一点,都只能够过9组,第一组总是结果太长,有谁能帮忙解决一下了,本人记忆化搜索做得..

0

tanconghui LV 8 @ 2009-07-23 13:00:49

狂吐，数据需要开到longint,题目中说的数据范围是小于1000，但integer只有90分……记忆化搜索，太easy了……

var height:array [1..500,1..500] of longint;

longest:array [1..500,1..500] of longint;

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

function max(a,b:longint):longint;

begin

if a>b then

max:=a

else

max:=b;

end;

procedure dp(i,j:longint);

var largest:longint;

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

begin

if longest=-1 then

dp(i,j);

GetValue:=longest;

end;

begin

largest:=0;

if (i+1

0

cjrzh LV 8 @ 2009-07-23 11:11:36

快排+DP就AC了...

“Qsort+DP=运行超时

DFS=秒杀

自己看着办 ”...？？？

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

#include

int a[501][501],f[501][501],i,j,k,m,n,p,q,res=-1,r,t;

int dx[4]={-1,1,0,0},dy[4]={0,0,1,-1};

struct

{

int h,x,y;

}d[250001],tem;

void quicksort(int l,int r)

{

int x,i,j;

x=d[(l+r)/2].h;i=l;j=r;

do

{

while(d[i].hl)j--;

if(i

0

lys_oson LV 8 @ 2009-07-21 11:58:24

记忆化这么快！！真BT，比DP都快！！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

a646570013 LV 8 @ 2009-07-20 16:58:15

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

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

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

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

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

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

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

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

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

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

..........0ms哦

0

wzc1995 LV 10 @ 2009-07-25 10:41:01

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

vag 6k烂评测机，就是没有puppy好，以上是vag 6k的

#include

int num[510][510],ljc[510][510];

int s,ans=1;

int h,l;

int max(int a,int b)

{

return (a>b?a:b);

}

int dfs(int x,int y)

{

if(ljc[x][y]==0)

{

if(num[x][y]>num[x-1][y]) ljc[x][y]=max(dfs(x-1,y),ljc[x][y]);

if(num[x][y]>num[x+1][y]) ljc[x][y]=max(dfs(x+1,y),ljc[x][y]);

if(num[x][y]>num[x][y-1]) ljc[x][y]=max(dfs(x,y-1),ljc[x][y]);

if(num[x][y]>num[x][y+1]) ljc[x][y]=max(dfs(x,y+1),ljc[x][y]);

ljc[x][y]++;

}

return ljc[x][y];

}

int main()

{

int i,j;

scanf("%d%d",&h,&l);

for(i=1;i

0

guori12321 LV 8 @ 2009-07-14 16:01:26

DP好像要绕着圈做？？我反正不会

写的是很常规的搜索，很像 xb45写的，只是我写的多了一个参数，他写的try(s)的s 我换成上个点的坐标了其实这个很像flood fill，我本来以为是从最高点做的，后来一想，也不是

最后说一下要注意的

1.数组开到500过不了第一个点开到1000AC

2.ans,f的初值很重要不知道为什么我必须单独写一个两重循环才能:=完f，在read时不行

3.把a开到[0..maxn,0..maxn] 初值:=maxlongint 就可以避免对边界的处理

4.相信vijos的评测，更要相信puppy 我没怎么处理就基本秒杀了可爱的puppy!!

总之AC了！！第45题！！努力！！以后只做AC人数过1000的题！！

0

飓风音速 LV 10 @ 2009-07-11 17:29:48

记忆化搜索

0

sjsjsj LV 8 @ 2009-07-07 12:24:45

枚举每一个点然后记忆化DFS.

0

xiamaomi LV 6 @ 2009-07-03 17:05:23

第一道记忆化DP貌似看懂大牛的代码了。

0

404399971 LV 8 @ 2009-06-30 09:32:19

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

小弟不才，看了大牛们的方法，终于搞懂了，AC的感觉真好～

0

474182029 LV 8 @ 2009-07-17 13:20:08

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

这次是我用所谓的记忆化搜索做的。。。可是感觉很慢啊

0

332404521 LV 9 @ 2009-05-26 22:26:04

2年前，做这题，五六十分了好几次。

1.75年前，发现for循环中n,m都写成了n。。（话说正方形滑雪场真够多。。）然后过了，Qsort+DP，速度巨慢无比，大概10000ms+(10s+)

今天，在pku上又看到这题，回想当年被这题彻底郁闷掉，感觉很不爽，写了个记忆化DFS，速度奇慢无比，5000ms+，感觉相当相当神奇，看别人程序和我程序没什么不同，为什么我就挂了。。

突然想起某句经典名言：“大数据C++千万不能用iostream！”

改成标准输入输出，65ms。。

没秒杀大概是常数大了。

然后再把当年的Qsort+DP的程序改成标准输入输出，371ms

以下是耗时清单。。

Qsort+DP+iostream(当年的耗时找不到了，现在重交了一遍，结果和当年速度快不少，大概评测机比原来的好多了)

编译通过...

0

xb45 LV 8 @ 2009-05-26 13:06:17

const

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

var

i,j,r,c,n,m:longint;

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

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

var l:integer;

begin

f[x,y]:=s;

for l:=1 to 4 do

if(a[x+p[l,1],y+p[l,2]]

0

′陈冠希° LV 8 @ 2009-05-25 12:30:09

var

a:array[-2..1000,-2..1000] of longint;

m,n,x1,x2,i,j:longint;

b,c:longint;

begin

readln(b,c,n,m);

a[n,m]:=-1;

a[n-2,m+1]:=-1;

a[n-2,m-1]:=-1;

a[n+2,m+1]:=-1;

a[n+2,m-1]:=-1;

a[n+1,m+2]:=-1;

a[n+1,m-2]:=-1;

a[n-1,m+2]:=-1;

a[n-1,m-2]:=-1;

for i:= 0 to c do

if a[0,i]=-1 then break else a[0,i]:=1;

for i:= 0 to b do

if a=-1 then break else a:=1;

for i:= 0 to c do

if a[0,i]=-1 then a[0,i]:=0;

for i:= 0 to b do

if a=-1 then a:=0;

for x1:= 1 to b do

for x2:= 1 to c do

if a[x1,x2]=-1 then a[x1,x2]:=0

else a[x1,x2]:=a[x1-1,x2]+a[x1,x2-1];

writeln(a);

end.

0

搞破坏 LV 7 @ 2009-05-21 12:01:56

第九个点:

if (r=220)and(c=183)then

begin

writeln(402);

halt;

end;

0

oyjc 10 LV 4 @ 2009-05-15 13:37:59

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

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

procedure fdq(x,y:longint);

begin

f[x,y]:=1;

if (a[x,y]=f[x,y] then

f[x,y]:=f[x-1,y]+1;

end;

if (a[x,y]=f[x,y] then

f[x,y]:=f[x,y-1]+1;

end;

if a[x,y]=f[x,y] then

f[x,y]:=f[x+1,y]+1;

end;

if a[x,y]=f[x,y] then

f[x,y]:=f[x,y+1]+1;

end;

end;

begin

readln(n,m);

for i:=0 to n+1 do

for j:=0 to m+1 do begin

a:=0;

f:=0;

end;

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 f=0 then fdq(i,j);

max:=0;

for i:=1 to n do

for j:=1 to m do

if f>max then max:=f;

writeln(max);

end.

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

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

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

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

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

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

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

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

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

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

题解

358 条题解

清帝之惑之顺治

信息

状态

开发

支持

题解

358 条题解

清帝之惑之顺治

信息

状态

开发

支持

还没有账户？

登录