讨论 / 程序AC80,最后两个点错了,帮忙找问题。
B03 2015-08-13 12:45:44
点我顶贴 收藏 删除
var

i,j,r,l,max,k,n:longint;

a,f:array[1..100,1..100] of longint;

b,c,d:array[1..10000] of longint;

procedure sort(l,r: longint);

var

i,j,x,y: longint;

begin

i:=l;j:=r;x:=b[(l+r) div 2];

repeat

while b[i]>x do inc(i);

while x>b[j] do dec(j);

if not(i>j) then begin

y:=b[i];b[i]:=b[j];b[j]:=y;

y:=c[i];c[i]:=c[j];c[j]:=y;

y:=d[i];d[i]:=d[j];d[j]:=y;

inc(i);j:=j-1;

end;

until i>j;

if l<j then sort(l,j);

if i<r then sort(i,r);

end;

begin

readln(r,l);

k:=0;

for i:=1 to r do begin

for j:=1 to l do begin

read(a[i,j]);

k:=k+1;

b[k]:=a[i,j];

c[k]:=i;

d[k]:=j;

end;

readln;

end;

n:=k;

sort(1,n);

for k:=1 to n do begin

max:=0;

i:=c[k];j:=d[k];

if (a[i,j]<a[i-1,j]) and (f[i-1,j]>max) then max:=f[i-1,j];

if (a[i,j]<a[i+1,j]) and (f[i+1,j]>max) then max:=f[i+1,j];

if (a[i,j]<a[i,j-1]) and (f[i,j-1]>max) then max:=f[i,j-1];

if (a[i,j]<a[i,j+1]) and (f[i,j+1]>max) then max:=f[i,j+1];

f[i,j]:=max+1;

end;

max:=0;

for i:=1 to r do

for j:=1 to l do if f[i,j]>max then max:=f[i,j];

write(max);

end.

f[i,j]表示以第i行、第j列的那个数结尾的最长滑坡。

#1 tchwr@2015-10-28 23:05:24
回复 删除
你换用记忆化搜索(动态规划+递归调用)试试看。

查看更多回复
提交回复