一、问题描述
某旅游区的街道成网格状（见图例）。其中东西向的街道都是旅游街，南北向的街道都是林荫道。由于游客众多，旅游街被规定为单行道，游客在旅游街上只能从西向东走，在林荫道上可以从南向北走，也可从北向南走。
阿隆想到这个旅游区游玩。他的好友阿福给了他一些建议，用分值表示所有旅游街相邻两个路口之间值得游览的程度，分值是从-100到100的整数，所有林荫道不打分。所有分值不可能全是负分。
例如下图是被打过分的某旅游区的街道图：
北
|
西 |
|
-50 -47 36 -30 -23 | ||||
|
17 |
-19 |
-34 |
-13 |
-8 |
|
-42 |
-3 |
-43 |
34 |
-45 |
南
阿隆可以从任一个路口开始游览，在任一个路口结束游览。请你写一个程序，帮助阿隆找一条最佳的游览路线，使得这条路线的所有分值总和最大。
二、分析
题很无聊，说白了就是竖直方向上没有权，想怎么走就怎么走，于是乎就只管水平方向。一开始真能把人糊弄了，但是仔细看，会发现只能从左向右走，既然如此，那就只能鉴定此题为水题一道！于是每一列只选一条最大权路即可。
设F(i)为第I列所有格线中最大分值。
由题可知，最大分值即为： Max{F[I]+F[I+1]+…+F[j]}(1<=I<=j<=n)
所以我们将问题转化为：求数列中连续最大和问题。
对于求连续最大和问题，很容易想到用动态规划。
设G(i)为以第I个数结尾的连续最大和。由于当G(I-1)>0时，G(i)就是G(I-1)基础上添加一个F(i)；而如果G(I-1)<=0，则G(i)只能取F(i)本身，否则就不是最大和。可得到如下递推方程：
G(i)=Max{G(I-1)+F(i),F(i)}(n>=I>1)
边界为 G(0)=0
三、参考程序
const finp ='input.txt';
fout ='output.txt';
maxN =20001;
var map :array[1..maxN]of shortint; {记录F表}
m,n :integer;
buffer :array[1..40960]of char;
s :longint;
procedure init; {输入}
var i,j :integer;
x :shortint;
begin
assign(input,finp);reset(input);
Settextbuf(input,buffer);
readln(m,n);
fillchar(map,sizeof(map),$80);
for i:=1 to m do begin
for j:=1 to n-1 do begin
read(x);
if x>map[j] then map[j]:=x
end;
readln
end;
close(input)
end;
procedure main;
var t :longint;
i :integer;
begin
s:=0;t:=0;
for i:=1 to n-1 do begin
if s+map[i]>map[i] then s:=s+map[i]
else s:=map[i]; {状态转移方程}
if s>t then t:=s {记录最优值}
end
end;
procedure out; {输出}
begin
assign(output,fout);rewrite(output);
writeln(s);
close(output)
end;
Begin {主程序}
init;
main;
out
End.
此题挺巧妙，不过就是一糊弄人的水题。