题目链接

代码：

#include <bits/stdc++.h>

using namespace std;

struct node {
	int x, y;
};

const int N = 15;
int a[N][N], dp[N][N];
vector<node> path[N][N];

int main() {
	int n;
	scanf("%d", &n);
	int x, y, v;
	while (scanf("%d%d%d", &x, &y, &v) == 3 && x != 0 && y != 0 && v != 0) {
		a[x][y] = v;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			printf("%d ", a[i][j]);
		}
		printf("\n");
	}
	int ret = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dp[i - 1][j] + a[i][j] >= dp[i][j - 1] + a[i][j]) {
				dp[i][j] = dp[i - 1][j] + a[i][j];
				vector<node>::iterator it;
				for (it = path[i - 1][j].begin(); it != path[i - 1][j].end(); it++) {
					path[i][j].push_back(*it);
				}
				node t;
				t.x = i;
				t.y = j;
				path[i][j].push_back(t);
			} else {
				dp[i][j] = dp[i][j - 1] + a[i][j];
				vector<node>::iterator it;
				for (it = path[i][j - 1].begin(); it != path[i][j - 1].end(); it++) {
					path[i][j].push_back(*it);
				}
				node t;
				t.x = i;
				t.y = j;
				path[i][j].push_back(t);
			}
		}
	}
	ret += dp[n][n];
	vector<node>::iterator it;
	for (it = path[n][n].begin(); it != path[n][n].end(); it++) {
		node temp = *it;
		a[temp.x][temp.y] = 0;
	}
	memset(dp, 0, sizeof(dp));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dp[i][j] = max(dp[i - 1][j] + a[i][j], dp[i][j - 1] + a[i][j]);
		}
	}
	ret += dp[n][n];
	printf("%d\n", ret);
	return 0;
}

是WrongAnswer