本蒟蒻来啦

#include <iostream>
using namespace std;
int n, m; 
int d[10][10]; //该数组记录每个网格的值
int f[10][10][10][10]; //四维动态规划，这个数组记录了四个坐标
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        d[x][y] = z;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            for (int l = 1; l <= n; l++)
            {
                for (int k = 1; k <= n; k++)
                {
                    // 根据动态规划的状态转移方程进行状态的转移
                    f[i][j][l][k] = max(max(f[i - 1][j][l - 1][k], f[i][j - 1][l][k - 1]), max(f[i - 1][j][l][k - 1], f[i][j - 1][l - 1][k])) + d[i][j];
                    if (i != l || j != k)
                    {
                        // 对于非对角线上的格子，它可以走两次取两次值，所以需要加上d[l][k]
                        f[i][j][l][k] += d[l][k];
                    }
                }
            }
        }
    }
    cout << f[n][n][n][n];
    return 0;
}

== 深搜是个好东西 ==

四种情况：

• 两种都向下走
• 两种都向右走
• 第一种向下走，第二种向右走
• 第一种向右走，第二种向下走

注意剪枝，即当重复枚举到一种情况时就直接返回，不然会 TLE 。

#include <iostream>
using namespace std;
int N = 0;
int s[15][15],f[11][11][11][11];
int dfs(int x,int y,int x2,int y2)
{
    if (f[x][y][x2][y2] != -1) return f[x][y][x2][y2]; 
    if (x == N && y == N && x2 == N && y2 == N) return 0;
    int M = 0; 
    if (x<N && x2<N) M = max(M,dfs(x+1,y,x2+1,y2)+s[x+1][y]+s[x2+1][y2]-s[x+1][y]*(x+1==x2+1&&y==y2));
    if (x<N && y2<N) M = max(M,dfs(x+1,y,x2,y2+1)+s[x+1][y]+s[x2][y2+1]-s[x+1][y]*(x+1==x2&&y==y2+1));
    if (y<N && x2<N) M = max(M,dfs(x,y+1,x2+1,y2)+s[x][y+1]+s[x2+1][y2]-s[x][y+1]*(x==x2+1&&y+1==y2));
    if (y<N && y2<N) M = max(M,dfs(x,y+1,x2,y2+1)+s[x][y+1]+s[x2][y2+1]-s[x][y+1]*(x==x2&&y+1==y2+1));
    f[x][y][x2][y2]=M;
    return M;
}
int main()
{
    int m;
    cin >> N >> m;
    for(int a = 0;a <= N;a++)
        for(int b = 0;b <= N;b++)
            for(int c = 0;c <= N;c++)
                for(int d = 0;d <= N;d++) 
                    f[a][b][c][d] = -1;
    for(int i = 0;i < m;i++)
    {
        int t1 = 0,t2 = 0,t3 = 0;
        cin >> t1 >> t2 >> t3;
        if(t1 == 0 && t2 == 0 && t3 == 0) break;
        s[t1][t2] = t3;
    }
    cout << dfs(1,1,1,1) + s[1][1];
    return 0;
}

==

接下来是本蒟蒻的第一偏题解(确信

#include <bits/stdc++.h>
using namespace std;
int a[10][10],f[10][10][10][10];
int main()
{
int n,m;
cin >> n >> m;
for(int i=1;i<=m;i++)
{
int x,y,Value;
cin >> x >> y >> Value;
a[x][y]=Value;//储存每一个数据的值
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
{
int l=i+j-k;//使两条线路上的数的移动步数相同用来压缩时间复杂度
if(l<=0)
{
break;
}
if(i==k&&j==l)//因为移动步数相同所以不可能出现在之前就走到a[i][j]的位置，这里的特判是指两次都走了同一条路，只会被取走一次
{
f[i][j][k][l]=max(max(f[i-1][j][k-1][l],f[i][j-1][k-1][l]),max(f[i-1][j][k][l-1],f[i][j-1][k][l-1]))+a[i][j];
}
else
{
f[i][j][k][l]=max(max(f[i-1][j][k-1][l],f[i][j-1][k-1][l]),max(f[i-1][j][k][l-1],f[i][j-1][k][l-1]))+a[i][j]+a[k][l];
}//否则都会取
}
cout << f[n][n][n][n];
}