题解

简单的DP。

状态设计：$dp_{i,j,k,l}$ 表示第一次走到 $(i,j)$，第二次走到 $(k,l)$ 的最大值。

转移方程就很显然了。

注意减去 $(i,j)$ 与 $(k,l)$ 重合的时候。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,x,y,z;
ll a[10][10],dp[10][10][10][10];
int main(){
    cin>>n;
    while(cin>>x>>y>>z){
        if(x+y+z==0) break;
        a[x][y]=z;
    }
    for(ll i=1;i<=n;i++) for(ll j=1;j<=n;j++) for(ll k=1;k<=n;k++) for(ll l=1;l<=n;l++) dp[i][j][k][l]=max({dp[i-1][j][k-1][l],dp[i][j-1][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k][l-1]})+a[i][j]+a[k][l]-a[i][j]*(i==k&&j==l);
    cout<<dp[n][n][n][n];
    return 0;
}