思路

从左上角到右下角,每次只能向左或者向右走,那么总步数一定是$2×n-1步$
用$f[k][i_1][i_2]$表示第$k$步时,从$[1,1]->[i_1][k+1-i_1],[i_2][k+1-i_2]$的总数之和
那么枚举每一步,只有当步数相同时,两条路径才有可能相交
$∵i+j-1=k \\\ ∴j=k+1-i$
状态转移方程:
$f[k][i_1][i_2] =max\begin{cases} f[k-1][i_1][i_2]\\\ [k-1][i_1][i_2-1]\\\ [k-1][i_1-1][i_2]\\\ [k-1][i_1-1][i_2-1]\end{cases} + w$
$ w= (i1==i2\ ?\ g[i_1][j_1]\ :\ (g[i_1][j_1]+g[i_2][j_2]))$

伪代码

    for k from 1 to 2*n-1
        for i1 from 1 to n
            for i2 form 1 to n
                j1 = k+1-i1
                j2 = k+1-i2
                f[k][i1][i2] = max{f[k-1][i1][i2],[k-1][i1][i2-1],[k-1][i1-1][i2],[k-1][i1-1][i2-1]}
                if i1 != i2 f[k][i1][i2] += g[i1][j1] + g[i2][j2]
                else f[k][i1][i2] += g[i1][j1]

C++ 代码

#include <iostream>
using namespace std;
const int maxn = 15;
int n;
int g[maxn][maxn];
int f[maxn*2][maxn][maxn]; 
//f[k][i1][i2] 表示走k步时
//从(1,1) 到 (i1,k-i1),(i2,k-i2)两点的和的最大值 
inline int max(int a,int b){return a>=b?a:b;}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    int a,b,w;
    while(cin>>a>>b>>w)
    {
        if(a==b && b==w && w==0) break;
        g[a][b] = w;
    }
    f[1][1][1] = g[1][1];
    for(int k=1;k<=2*n-1;++k)
        for(int i1=1;i1<=n;++i1)
            for(int i2=1;i2<=n;++i2)
            {
                int j1=k-i1+1 , j2 = k-i2+1;
                if(j1<1 || j1>n || j2<1 || j2>n) continue;
                int w = g[i1][j1];
                if(i1 != i2) //汇聚不同点 
                    w += g[i2][j2];
                int& s = f[k][i1][i2];
                s = max(s,f[k-1][i1][i2] + w);
                s = max(s,f[k-1][i1-1][i2] + w);
                s = max(s,f[k-1][i1][i2-1] + w);
                s = max(s,f[k-1][i1-1][i2-1] + w);
            }
    cout<<f[2*n-1][n][n]<<endl;
    return 0;
}