思路:

比较细节的一个题目,类似<传纸条>.但是<传纸条>那题点权只有正数,而这题点权有负数,我们还是设立和传纸条那题的方程.
令表示到了第步,第一个位于的行的位子,第二个位于行的位子能够获得的.
那么方程真的很好写,这里就不叙述了.

细节

1.因为这里有负权,不是说两条路不重合,所以说两条路是可以重合的.
2.假如你跟我楼下代码写的一样,别忘了开两倍,因为可能会大于哦.

代码:

#include <bits/stdc++.h>
using namespace std;
const int N=310;
int val[N<<1][N<<1];
int f[N<<1][N][N];
int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>val[i][j];
    memset(f,-0x3f,sizeof f);
    f[2][1][1]=2*val[1][1];
    for(int i=2;i<=2*n;i++)
    {
        for(int j=1;j<=n&&j<i;j++)
        {
            for(int k=1;k<=n&&k<i;k++)
            {
                f[i][j][k]=max(f[i][j][k],f[i-1][j][k]+val[i-j][j]+val[i-k][k]);
                f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k-1]+val[i-j][j]+val[i-k][k]);
                f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k]+val[i-j][j]+val[i-k][k]);
                f[i][j][k]=max(f[i][j][k],f[i-1][j][k-1]+val[i-j][j]+val[i-k][k]);
                if(j==k)    f[i][j][k]-=val[i-k][k];
            }
        }
    }cout<<f[2*n][n][n]<<'\n';
    return 0;
}