小茗同学正在玩牧场物语。该游戏的地图可看成一个边长为n的正方形。
小茗同学突然心血来潮要去砍树，然而，斧头在小茗的右下方。
小茗是个讲究效率的人，所以他会以最短路程走到右下角，然后再返回到左上角。并且在路上都会捡到/踩到一些物品，比如说花朵，钱和大便等。
物品只能被取最多一次。位于某个格子时，如果格子上还有物品，就一定要取走。起点和终点上也可能有物品。
每种物品我们将为其定义一个价值，当然往返之后我们取得的物品的价值和越大越好。但是小茗同学正在认真地玩游戏，请你计算出最大的价值和。
Input
多组数据(<=10)，处理到EOF。
第一行输入正整数N(N≤100)，表示正方形的大小。
接下来共N行，每行N个整数Ai,j(|Ai,j|≤10^9)，表示相应对应位置上物品的价值。值为0表示没有物品。
Output
每组数据输出一个整数，表示最大价值和。
Sample Input
2
11 14
16 12
Sample Output
53
这道题做了好久都没做出来，最后还是看的题解才做出了的。
这种多线程的dp还是第一次见。。。。
题目分析：
- 状态表示：这道题小茗来回走了两遍图，我们可以将其看作是有两个人从起点走到了终点。两人的话dp就要记录两人的位置，这样数组就是四维的。但是我们可以只记录走的步数和两人位置的横坐标x，用步数和横坐标就可以算出两人位置的纵坐标来，这样状态就简化成了三维的
f[i][j][k] //i,j分别表示两人的横坐标，k表示两人走的步数 - 状态计算：然后是计算状态方程。
1） f[i][j][k]有四种表示状态：
f[i][j][k-1] //两人都往下走
f[i-1][j][k-1] //第一个人往右走，第二个人往下走
f[i][j-1][k-1] //第一个人往下走，第二个人往右走
f[i-1][j-1][k-1] //两人都往右走
然后f[i][j][k]只需要取这四种状态中的最大值即可
2）最后是加上两人当前位置的价值值
当i==j时，说明两人位置相同，只需要加上一个人的即可 a[i][k-i+2]
当i!=j时，两人位置不同，因此两个人的都要加上 a[i][k-i+2]+a[j][k-j+2]
ac代码：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
#include <iomanip>
#define LL long long
const int N=105;
using namespace std;
LL f[N][N][N<<1],a[N][N]; //注意要用long long
int main()
{int n;while(cin>>n){memset(f,-0x3f,sizeof f); //初始化,因为答案可能是负数for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];f[1][1][0]=a[1][1]; //初始化for(int k=1;k<=2*n-2;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(i==j) f[i][j][k]=(a[i][k-i+2]);else f[i][j][k]=a[i][k-i+2]+a[j][k-j+2];f[i][j][k]+=max(max(f[i][j][k-1],f[i-1][j-1][k-1]),max(f[i-1][j][k-1],f[i][j-1][k-1]));}cout<<f[n][n][2*n-2]<<endl;}return 0;
}
