RT大概思路是把dp[i][j]时网格的状态存下来。。 然后直接正常dp。。(虽然这个做法有点蠢

#include<bits/stdc++.h>
namespace IO {
	inline int read() {
		int ret = 0, f = 1;char ch = getchar();
		while (ch < '0' || ch > '9') {
			if (ch == '-') f = -f;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') {
			ret = (ret << 1) + (ret << 3) + (ch ^ 48);
			ch = getchar();
		}
		return ret * f;
	}
	void write(int x) {
		if (x < 0) x = -x;
		if (x > 9) write(x / 10);
		putchar(x % 10 + '0');
	}
}

using namespace IO;
using namespace std;
const int maxn = 9 + 1;

int n;
int g[maxn][maxn][maxn][maxn];
int dp[maxn][maxn];
int main() {
	n = read();
	while (1) {
		int x = read(), y = read(), s = read();
		if (x == y && y == s && s == 0) break;
		g[0][0][x][y] = s;
	}
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= n;j++) {
			int k = g[0][0][i][j];
			for (int k = 1;k <= n;k++) g[0][k][i][j] = k, g[k][0][i][j] = k;
		}
	}
	for (int i = 1; i<= n;i++) dp[1][i] = g[0][0][1][i], dp[i][1] = g[0][0][i][1];
	for (int i = 2;i <= n;i++) {
		for (int j = 2;j <= n;j++) {
			if (dp[i][j - 1] > dp[i - 1][j]) for (int k = 1;k <= n;k++) for (int l = 1;l <= n;l++) g[i][j][k][l] = g[i][j - 1][k][l];
			else for (int k = 1;k <= n;k++) for (int l = 1;l <= n;l++) g[i][j][k][l] = g[i - 1][j][k][l];
			dp[i][j] += max(dp[i - 1][j], dp[i][j - 1]) + g[i][j][i][j];
			g[i][j][i][j] = 0;
		}
	}
	for (int i = 2;i <= n;i++) {
		for (int j = 2;j <= n;j++) {
			if (dp[i][j - 1] > dp[i - 1][j]) for (int k = 1;k <= n;k++) for (int l = 1;l <= n;l++) g[i][j][k][l] = g[i][j - 1][k][l];
			else for (int k = 1;k <= n;k++) for (int l = 1;l <= n;l++) g[i][j][k][l] = g[i - 1][j][k][l];
			dp[i][j] += max(dp[i - 1][j], dp[i][j - 1]) + g[i][j][i][j];
			g[i][j][i][j] = 0;
		}
	}
	
//	printf("%d\n", dp[n][n]);
	write(dp[n][n]);
	return 0;
}