题目描述
话说在军训的倒数第二天，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个整数，每两个整数之间用一个空格隔开。
输出
一行一个整数表示最大好感度和。注意，起点和终点的好感度值只计入一次。
样例输入
3 4
1 2 3 4
5 6 7 8
9 10 11 12
样例输出
71
数据范围限制
2<=n,m<=50。
好感度为10000以内的正整数。
题解：
DP，设f[i,j,k,l]表示两个人从起点分别走到坐标为（i，j）（k，l）且路径不重复时的最大好感度。
题解：
function max(x,y:longint):longint;
beginif x>y then exit(x);exit(y);
end;
vari,j,k,l,m,n:longint;f:array[0..60,0..60,0..60,0..60] of longint;a:array[0..60,0..60] of longint;
beginassign(input,'paint.in');reset(input);assign(output,'paint.out');rewrite(output);readln(m,n);for i:=1 to m dofor j:=1 to n doread(a[i,j]);for i:=1 to m dofor j:=1 to n dofor k:=1 to m dofor l:=1 to n dobeginf[i,j,k,l]:=max(max(f[i,j-1,k,l-1],f[i,j-1,k-1,l]),max(f[i-1,j,k,l-1],f[i-1,j,k-1,l]))+a[i,j];if (i<>k)or(j<>l) then inc(f[i,j,k,l],a[k,l]);end;writeln(f[m,n,m,n]);close(input);close(output);
end.