看到题目，就会发现，又是一道数字三角形模型的题目

但不同以往，这次允许我们从起点出发两次，所以需要在原来的基础上做一些变形

关于当前的状态如何表示：

一开始一般会想到用四维数组f[x1][y1][x2][y2]来记录两条路线当前走到位置的坐标

但是题目中有一个限制，那就是对于两次路线都经过的点，其价值只会被累加一次

如果用四个坐标来表示当前的状态，那我们还需要额外开一维来记录当前矩阵中哪些格子被取过数了

即 f[x1][y1][x2][y2][1 << (n * n)]

关于这种状态压缩的做法我就不再展开了，明眼人都看出来，时间复杂度和空间复杂度会爆掉

题目要求我们从起点先后出发两次

但我们可以规定两次是同时出发的，因为这两种方案的所有路线都是一一对应的

为什么这么映射呢？因为这样子做的话，我们可以轻松的处理两次路线走到同一个格子的情况

由此我们就可以把路径长度，作为DP的阶段

每个阶段中，我们同时把两条路径扩展一步，即路径长度加 $1$ ，来进入下一个阶段

而路径长度加$1$后，无非就是向下走一格或是向右走一格，对应横纵坐标的变换

根据$k,x_1,y_1,x_2,y_2$的关系，我们可以获得如下等式

$$ x_1 + y_1 = x_2 + y_2 = k $$

获得上述等式以后，我们就可以通过三个维度来描述状态了，分别是$k, x_1, x_2$

于是，状态的初值为f[2][1][1]，目标状态为f[2 * n][n][n]

则对于如何判断两次路线走进了同一个方格里，可以通过$x_1 = x_2$来判断了

1. 当$x_1 \ne x_2$，当前两条路线走到的格子不是同一个，则$\mathrm{w} = w(x_1,k-x_1) + w(x_2,k-w_2)$
2. 当$x_1=x_2$，当前两条路线走到了同一个格子中，则$\mathrm{w} = w(x_1,k-x_1)$

而状态转移，基本参照数字三角形的模型即可，具体的我贴出闫氏DP分析法思维导图

闫氏DP分析法

$$ \begin{cases} 状态表示f_{k,i,j} \begin{cases} 属性: 路径长度为k,第一条路线到x_1=i,第二条路线到x_2=j的所有方案 \\\ 集合: 方案中的路线经过的所有物品的总价值最大 Max \end{cases} \\\ 状态转移 f_{k,i,j} = max\{f_{k-1,i,j},f_{k-1,i-1,j},f_{k-1,i,j-1},f_{k-1,i-1,j-1}\} + w \end{cases} $$

集合划分

#include <bits/stdc++.h>
using namespace std;
#define ls u << 1
#define rs u << 1 | 1
#define LL long long
#define int long long
#define PII pair <int, int>
#define fi first
#define se second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define i128 __int128
#define pcnt(x) __builtin_popcount(x)
#define mem(a,goal) memset(a, (goal), sizeof(a))
#define rep(x,start,end) for(int x = (start) - ((start) > (end)); x != (end) - ((start) > (end)); ((start) < (end) ? x ++ : x --))
#define aLL(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
const int INF = 998244353;
const int mod = 1e9 + 7;
const int N = 100010;
void solve()
{
    int n;
    cin >> n;
    int f[n + n + 1][n + 1][n + 1] = {0};
    int g[n + 1][n + 1] = {0};
    int a, b, c;
    while(cin >> a >> b >> c, a || b || c) g[a][b] =c;

    for(int k = 2; k <= n + n; ++ k)
    {
        for(int x1 = 1; x1 <= n; ++ x1)
        {
            for(int x2 = 1; x2 <= n; ++ x2)
            {
                int y1 = k - x1, y2 = k - x2;
                if(y1 < 1 || y1 > n || y2 < 1 || y2 > n) continue;
                
                int val = g[x1][y1];
                if(x1 != x2) val += g[x2][y2];
                int &t = f[k][x1][x2];

                t = max(t, f[k - 1][x1 - 1][x2] + val);
                t = max(t, f[k - 1][x1][x2 - 1] + val);
                t = max(t, f[k - 1][x1 - 1][x2 - 1] + val);
                t = max(t, f[k - 1][x1][x2] + val);
            }
        }
    }
    
    cout << f[n + n][n][n] << '\n';
}
signed main()
{
    int t = 1;
    while (t --) solve();
    return 0;
}