题解

#include <iostream>
using namespace std;
int n,i,j,tmp,k,l;
int puz[20][20], dp[20][20][20][20];
int main()
{
       scanf("%d",&n);
       while(scanf("%d%d%d", &i, &j, &tmp) && i)
        puz[i][j] = tmp;
    
          for(i = 1;i <= n; i++)
              for(j = 1; j <= n; j++)
                  for(k = 1; k <= n; k++)
                      for(l = 1; l <= n; l++) {
                              dp[i][j][k][l] = max(max(dp[i-1][j][k-1][l],dp[i][j-1][k][l-1]),
                                                                               max(dp[i-1][j][k][l-1],dp[i][j-1][k-1][l]))+puz[i][j];
                             if(i != k||j != l) dp[i][j][k][l] += puz[k][l];
                             }
        printf("%d\n", dp[n][n][n][n]);
        return 0;
}