题目描述

话说在军训的倒数第二天，zy终于下定决心要将画了10天之久的画像送给他心怡的法学院mm。但是，他不敢自己一个人去，倒霉的kk只能和他一起去了。不过，为了表现的有诚意，kk和zy不能走在一起，要不然被对方看见就不好了。那么到底要怎么走呢？zy给了kk一幅地图，他把学校分成了n*m个格子，对于每个格子，zy写下了一个数字表示他对于这个格子的好感度（好感度当然是zy自己定义的），入口在左上角（1,1）点，出口在右下角（n,m），zy和kk需要从左上角一起出发，在右下角会和，因为zy非常害羞，所以中间kk和zy都只向右或向下走，这样走完全程的时间最短，但中间两人不能走到同一个格子上。经过深思熟虑，他决定，需要他和kk走的路的好感度总和最大才是最好。现在，zy和kk希望你能告诉他们两个人各自要走那一条路。为了简化问题，你只需告诉他们两个好感度总和就可以了。你可以假设mm一定会在zy的路上。

输入

第一行两个整数n,m。
接下来n行每行m个整数，每两个整数之间用一个空格隔开。

输出

一行一个整数表示最大好感度和。注意，起点和终点的好感度值只计入一次。

思路

一个四维dp，和普通的最短路径问题相似，就是要多枚举一条路而已

onst
  maxn=51;
type 
  arraytype=array [0..maxn,0..maxn] of longint;
var 
  i,j,k,n,i1,i2,j1,j2,m:longint;
  data:arraytype;
  sum:array [0..maxn,0..maxn,0..maxn,0..maxn] of longint;
function max(x,y:longint):longint;
begin
  if x>y then max:=x else max:=y;
end;
begin 
  assign(input,'paint.in'); reset(input);
  assign(output,'paint.out'); rewrite(output);
  for i:=1 to maxn do
    for j:=1 to maxn do 
      data[i,j]:=0;
  readln(n,m);
  for i:=1 to n do
    begin
      for j:=1 to m do 
        read(data[i,j]);
      readln; 
    end;
  fillchar(sum,sizeof(sum),0);
  for i1:=1 to n do
    for j1:=1 to m do
      for i2:=1 to n do
        for j2:=1 to m do
          begin
            if sum[i1-1,j1,i2-1,j2]>sum[i1,j1,i2,j2]
              then sum[i1,j1,i2,j2]:=sum[i1-1,j1,i2-1,j2];
            if sum[i1-1,j1,i2,j2-1]>sum[i1,j1,i2,j2]
              then sum[i1,j1,i2,j2]:=sum[i1-1,j1,i2,j2-1];
            if sum[i1,j1-1,i2-1,j2]>sum[i1,j1,i2,j2]
              then sum[i1,j1,i2,j2]:=sum[i1,j1-1,i2-1,j2];
            if sum[i1,j1-1,i2,j2-1]>sum[i1,j1,i2,j2]
              then sum[i1,j1,i2,j2]:=sum[i1,j1-1,i2,j2-1];
            sum[i1,j1,i2,j2]:=sum[i1,j1,i2,j2]+data[i1,j1];
            if (i1<>i2) or (j1<>j2)
              then sum[i1,j1,i2,j2]:=sum[i1,j1,i2,j2]+data[i2,j2]
          end;
  writeln(sum[n,m,n,m]);
end.