问题描述
话说在军训的倒数第二天，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以内的正整数。
这道题与08年noip传纸条相当相似，虽然我并没有做过传纸条。
我是用递归做的，枚举两个人在一个时间点到的点，
如果相同就返回。
设置坐标0，0为之前已经到了终点，就只需要搜另一个人的路径了，
当某人到了终点时，下一次坐标就会为0，0，也是只需搜另一个人的路径了。
再加记忆数组，过完。
#include <iostream>
#include <fstream>
#include <cstdlib>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std; ifstream fin("paint.in");
ofstream fout("paint.out"); int cnt_heng=,cnt_lie=;
int jiyi[][][][]={};
int jv[][]; int dp(int he1,int zo1,int he2,int zo2){
if(he1==cnt_heng&&zo1==cnt_lie)
if(he2==cnt_heng&&zo2==cnt_lie)return jv[cnt_heng][cnt_lie];
if(he1==he2&&zo1==zo2)return ;
if(he1>cnt_heng||he2>cnt_heng)return ;
if(zo2>cnt_lie||zo1>cnt_lie)return ;
if(jiyi[he1][zo1][he2][zo2]!=)return jiyi[he1][zo1][he2][zo2];
int a[]={,},b[]={,};
int tem=;
if(he1==cnt_heng&&zo1==cnt_lie){
if(he2==&&zo2==)return ;
for(int x=;x<=;x++)
tem=max(tem,dp(,,he2+a[x],zo2+b[x]));
jiyi[he1][zo1][he2][zo2]=tem+jv[he1][zo1]+jv[he2][zo2];
return tem+jv[cnt_heng][cnt_lie]+jv[he2][zo2];
} if(he2==cnt_heng&&zo2==cnt_lie){
if(he1==&&zo1==)return ;
for(int x=;x<=;x++)
tem=max(tem,dp(he1+a[x],zo1+b[x],,));
jiyi[he1][zo1][he2][zo2]=tem+jv[he1][zo1]+jv[he2][zo2];
return tem+jv[cnt_heng][cnt_lie]+jv[he1][zo1];
}
if(he1==&&zo1==){
for(int x=;x<=;x++)
tem=max(tem,dp(,,he2+a[x],zo2+b[x]));
jiyi[he1][zo1][he2][zo2]=tem+jv[he2][zo2];
return tem+jv[he2][zo2];
}
if(he2==&&zo2==){
for(int x=;x<=;x++)
tem=max(tem,dp(he1+a[x],zo1+b[x],,));
jiyi[he1][zo1][he2][zo2]=tem+jv[he1][zo1];
return tem+jv[he1][zo1];
} for(int x=;x<=;x++)
for(int y=;y<=;y++){
tem=max(tem,dp(he1+a[x],zo1+b[x],he2+a[y],zo2+b[y]));
}
jiyi[he1][zo1][he2][zo2]=tem+jv[he1][zo1]+jv[he2][zo2];
return tem+jv[he1][zo1]+jv[he2][zo2];
} int main(int argc, char** argv) {
fin>>cnt_heng>>cnt_lie;
for(int x=;x<=cnt_heng;x++)
for(int y=;y<=cnt_lie;y++)fin>>jv[x][y]; int ans=dp(,,,);
ans+=jv[][];
cout<<ans;
fout<<ans; return ;
}