Question

求一道free pascal题目的源代码

描述 Description
trs喜欢滑雪。他来到了一个滑雪场，这个滑雪场是一个矩形，为了简便，我们用r行c列的矩阵来表示每块地形。为了得到更快的速度，滑行的路线必须向下倾斜。
例如样例中的那个矩形，可以从某个点滑向上下左右四个相邻的点之一。例如24-17-16-1，其实25-24-23…3-2-1更长，事实上这是最长的一条。

输入格式 Input Format
输入文件

第1行: 两个数字r，c(1<=r,c<=100)，表示矩阵的行列。
第2..r+1行:每行c个数，表示这个矩阵。

输出格式 Output Format
输出文件

仅一行: 输出1个整数，表示可以滑行的最大长度。
样例输入 Sample Input
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
样例输出 Sample Output
25

向各位大牛们请教这道题，要PASCAL的源代码。
顺便讲一下本题中使用的动态规划的具体方法。

Answer 1

DP

program phx;
var i,j,temp,n,m,max1:longint;
data,f:array [1..100,1..100] of longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;

function dp(i,j:longint):longint;
var l1,l2,l3,l4:longint;
begin
if f[i,j]<>maxlongint
then exit(f[i,j]);
l1:=1;
l2:=1;
l3:=1;
l4:=1;
if (i<>n) and (data[i+1,j]<data[i,j])
then l1:=l1+dp(i+1,j);
if (j<>m) and (data[i,j+1]<data[i,j])
then l2:=l2+dp(i,j+1);
if (i<>1) and (data[i-1,j]<data[i,j])
then l3:=l3+dp(i-1,j);
if (j<>1) and (data[i,j-1]<data[i,j])
then l4:=l4+dp(i,j-1);
f[i,j]:=max(max(l1,l2),max(l3,l4));
exit(f[i,j]);
end;

begin
readln(n,m);
for i:=1 to n do
for j:=1 to m do
begin
read(data[i,j]);
f[i,j]:=maxlongint;
end;

max1:=-maxlongint;
for i:=1 to n do
for j:=1 to m do
begin
temp:=dp(i,j);
if temp>max1 then
max1:=temp;
end;
writeln(max1);
end.

Answer 2

典型的记忆化搜索。
program exp;
var
i,j,n,m,max,smax:longint;
a,f:array[0..500,0..500] of longint;{f[i,j]表示坐标为(i,j)的这个点可以滑行的最大距离}
function search(x,y:longint):longint;{搜索从（x，y）这个点开始能滑的最大距离}
var
k,max:longint;
begin
if f[x,y]<>0 then search:=f[x,y] {如果已经搜过了就不必再搜了，直接读取搜过的数据}
else
begin
max:=0;
{接下来向四个方向搜}
if (a[x-1,y]<a[x,y])and(x-1>0) then
begin
k:=search(x-1,y)+1; {这递归应该看得懂吧，都学DP了}
if k>max then max:=k;
end;
if (a[x,y-1]<a[x,y])and(y-1>0) then
begin
k:=search(x,y-1)+1;
if k>max then max:=k;
end;
if (a[x,y+1]<a[x,y])and(y+1<=m) then
begin
k:=search(x,y+1)+1;
if k>max then max:=k;
end;
if (a[x+1,y]<a[x,y])and(x+1<=n) then
begin
k:=search(x+1,y)+1;
if k>max then max:=k;
end;
search:=max;
end;
end;
begin
readln(n,m);
for i:=1 to n do
for j:=1 to m do
read(a[i,j]);
max:=-1; smax:=-1;
for i:=1 to n do
for j:=1 to m do {搜索从每个点开始能滑的最大距离}
begin
f[i,j]:=search(i,j); {把搜索到的值记忆下来，以后不必再搜}
if f[i,j]>smax then smax:=f[i,j]; {获取最大值}
end;
writeln(smax+1); {加一是因为像上面这个例子，从25滑到1要走24步，却有25格}
end.

Answer 3

应该说是“记忆化搜索”吧……