分析：根据题意，与摘花生相比，该题可以走两次，但是每个格子上的值只能取一次。这里采用同时走的方法。
记第一条路线到达的点是(i1,j1) , 第二条路线到达的点是(i2,j2)
那么状态表示则为：f[i1][j1][i2][j2]，表示从(1,1)分别到(i1,j1)和(i2,j2)的最大值
根据题意，我们要处理的情况是当走到相同点的时候，可知到且仅当i1+j1=i2+j2时两条路线到达的点相交，于是引入一个参数k=i1+j1=i2+j2

那么状态表示可以转化成：f[k][i1][i2]，每个状态从前一步操作转移而来

状态划分：两条路线分别有向右和向下的选择，因此总共有四种选择：
1.第一条：向右，第二条向右
2.第一条：向右，第二条向下
3.第一条：向下，第二条向右
4.第一条：向下，第二条向下

而且当i1==i2，即两点重合时仅加一次

状态转移：根据状态划分依次转移，共有四条

C++ 代码

#include <iostream>

using namespace std;

const int N = 15;

int f[N*2][N][N];
int g[N][N];
int n;

int main()
{
    cin >> n;

    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 i1 = 1 ; i1 <= n ; i1++)
            for(int i2 = 1 ; i2 <= n ; i2++)
            {
                int j1 = k - i1 , j2 = k - i2;
                if(j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n)
                {
                    int t = g[i1][j1];
                    if(i1 != i2) t += g[i2][j2];//两点重合
                    int &x = f[k][i1][i2];
                    x = max(x , f[k - 1][i1 - 1][i2] + t);
                    x = max(x , f[k - 1][i1][i2 - 1] + t);
                    x = max(x , f[k - 1][i1 - 1][i2 - 1] + t);
                    x = max(x , f[k - 1][i1][i2] + t);
                }
            }

    cout << f[n + n][n][n] << endl;
    return 0;
}