我的方法$n<=400$都能AC
CPU i7-7660U
P1004传送门

#include <iostream>
#include <cstdio>
using namespace std;
int n;
int a[15][15];
int f[15][15];
int main() {
	scanf("%d",&n);
	while (true) {
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		if (x == 0) break;
		a[x][y] = w;
	}
	for (int step = 2; step < 2 * n; step++) {
		int l = max(1,step - n);
		int r = min(n,step);
		for (int i = r; i >= l; i--) {
			for (int j = r; j >= i + 1; j--) {
				int v = max(max(f[i][j],f[i][j - 1]),
							max(f[i - 1][j],f[i - 1][j - 1]));
				f[i][j] = v + a[i][step - i] + a[j][step - j];
			}
		}
	}
	int ans = f[n - 1][n] + a[n][n];
	printf("%d",ans);
	return 0;
}

@Zhaohongrui