DP。

#include<bits/stdc++.h>
#define wzry tqz_poet
using namespace std;
int dp[11][11][11][11];
int f[11][11];
int n, p, o, u;
int main(){
    int n;
    cin>>n;
    while(1){
        cin>>p>>o>>u;
        if(p==0&&u==0&&o==0) break;
        else f[p][o]=u;
    }
    for(int x=1;x<=n;x++){
        for(int y=1;y<=n;y++){
            for(int a=1;a<=n;a++){
                int b=x+y-a;
                if(b<0) break;
                dp[x][y][a][b]=max(dp[x-1][y][a-1][b],max(dp[x-1][y][a][b-1],max(dp[x][y-1][a-1][b],dp[x][y-1][a][b-1])));
                if(x==a&&y==b) dp[x][y][a][b]+=f[x][y];
                else dp[x][y][a][b]+=f[x][y]+f[a][b];
            }
        }
    }
    cout<<dp[n][n][n][n];
    return 0;
}