代码

#include <bits/stdc++.h>
using namespace std;
int a[15][15],f[15][15][15][15];
int i,j,k,h;
int main(int argc, char **argv){
	int n;
	cin >> n;
	int x;
	while (cin >> i && cin >> j && cin >> x){
		a[i][j] = x;
	}
	for (i = 1;i <= n;i++){
		for (j = 1;j <= n;j++){
			for(k = 1;k <= n;k++){
				for(h = 1;h <= n;h++){
					f[i][j][k][h] = max({f[i - 1][j][k - 1][h],f[i - 1][j][k][h - 1],f[i][j - 1][k - 1][h],f[i][j - 1][k][h - 1]}) + a[i][j];
					if (i != k && j != h)	f[i][j][k][h] += a[k][h];
				}
			}
		}
	}
	cout << f[n][n][n][n];
	return 0;
}

参考与鸣谢

本题解参考了《信息学竞赛一本通》中【例 9.21】的代码