算法：线性DP $时间复杂度O(2n ^ 3)$

将原问题抽象为，两条路的摘花生问题。所以暴力枚举的话是四维$n^4$的DP，目测也是可以过的
优化：两条路同时向前迈进。仍不违反DP的无后效性。所以DP成立。将四维优化成三维。
f[i][x1][x2],i:步长，x1:第一条路的横坐标，x2:第二条路的横坐标。

#include <bits/stdc++.h>

using namespace std;

const int N = 15;

int g[N][N];

int f[N << 1][N][N];

int main(){

    ios :: sync_with_stdio(false);
    cin.tie(0);

    int n;

    cin >> n;

    int a,b,c;

    while(cin >> a >> b >> c,a || b || c)
    {
        g[a][b] = c;
    }

    for(int i=2;i<=n << 1;i++)
        for(int x1 = 1;x1 <= n;x1 ++)
            for(int x2 = 1;x2 <= n;x2 ++)
            {
                int y1 = i - x1;
                int y2 = i - x2;
                int v = g[x1][y1];
                if(x1 != x2) v += g[x2][y2];
                if(i == 2) f[i][x1][x2] = g[1][1];
                else
                {
                    int t = 0;
                    t = max(t,f[i - 1][x1][x2]);
                    t = max(t,f[i - 1][x1 - 1][x2]);
                    t = max(t,f[i - 1][x1][x2 - 1]);
                    t = max(t,f[i - 1][x1 - 1][x2 - 1]);
                    f[i][x1][x2] = t + v;

                }
            }

    cout << f[n << 1][n][n] << endl;

    return 0;
}