链接:Link 耗时:0.028s
一道简单的动态规划,主要思路就是:用 $f[i,j]$ 表示到达 $(i,j)$ 的最长路径的长度。找到每个最高点,从其开始向四周的低处搜索。如果该点已搜过并且f值大于当前长度则退出回溯。直到达到某个最低点为止。
不多说了,直接上代码:
const delta :array [1..4, 1..2] of integer = ((-1, 0), (1, 0), (0, 1), (0, -1)); //四个方向向量var _: Integer; name: string; n, m, i, j, x: Integer; ans: longint; map: array [0..101, 0..101] of integer; f: array [1..100, 1..100] of longint;function max(x, y: longint): longint; inline;begin if x>y then exit(x) else exit(y);end;function can(x, y: integer): Boolean; inline; //判断是否是最高点var i: Integer; tx, ty: integer;begin can := true; for i := 1 to 4 do begin tx := x + delta[i, 1]; ty := y + delta[i, 2]; can := can and (map[x, y] >= map[tx, ty]); if not can then break; end;end;procedure dp(x, y: integer; len: longint); //回溯进行动态规划var i: Integer; tx, ty: integer;begin inc(len); if f[x, y] > len then exit; f[x, y] := len; ans := max(ans, len); for i := 1 to 4 do begin tx := delta[i, 1] + x; ty := delta[i, 2] + y; if (tx = 0) or (tx > n) or (ty = 0) or (ty > m) then continue; if map[x, y] <= map[tx, ty] then continue; dp(tx, ty, len); end;end;procedure ReadAndProcessName; //处理那行该死的名字!!var s: string; i: integer;begin readln(s); i := 1; name := ''; n := 0; m := 0; while s[i] <> ' ' do begin name := name + s[i]; inc(i); end; inc(i); while s[i] <> ' ' do begin n := n * 10 + ord(s[i]) - ord('0'); inc(i); end; inc(i); while i <= length(s) do begin m := m * 10 + ord(s[i]) - ord('0'); inc(i); end;end;begin assign(input, 'main.in');reset(input); assign(output, 'main.out');rewrite(output); readln(_); while _>0 do begin dec(_); fillchar(map, sizeof(map), 0); ReadAndProcessName; for i := 1 to n do for j := 1 to m do begin read(x); map[i, j] := x+1; end; readln; fillchar(f, sizeof(f), 0); ans := 0; for i := 1 to n do for j := 1 to m do if can(i, j) then dp(i, j, 0); writeln(name, ': ', ans); end; close(input);close(output);end.
OOPS!
A comment box should be right here...But it was gone due to network issues :-(If you want to leave comments, make sure you have access to disqus.com.