题目大意

有一个 n×n 的方格图，每个格子都有一个对应的权值 ai,j​，你从 (1,1) 开始走，每次可以从 (i,j) 走到 (i+1,j) 或 (i,j+1)，最终走到 (n,n)，你需要这样走两次，求你所经过的格子上的权值之和的最大值，每个格子上的权值只计算一次。

题目分析

1. 状态：定义一个四维数组 f，fi j k l​ 表示第一次走到第 i 行，第 j 列，第二次到达第 k 行，第 l 列能获得的最大值。

2. 状态转移方程：我们要考虑以下四种情况：

• 第一次从左边过来，第二次从左边过来

• 第一次从左边过来，第二次从上边过来

• 第一次从上边过来，第二次从左边过来

• 第一次从上边过来，第二次从上边过来

那么我们就要取这四种情况的最大值了，即：fi j k l​=max{fi−1 j k−1 l​,fi−1 j k l−1​,fi j−1 k−1 l​,fi j−1 k l−1​}+ai j​+ak l​。

但要注意的是，如果 (i,j)=(k,l)，那么就只能加其中一个（不能重复），所以此时要在原来的基础上减去一个 ai j​。

1. 初始化：刚开始也就是到点 (1,1) 能获得的最大值，即 f1 1 1 1​=0。

2. 答案：由于我们要求第一次和第二次走到右下角的最大值，所以我们的答案为 fn n n n​。

   #include <bits/stdc++.h> 
   using namespace std;
   
   int n, x, y, w, a[35][35], f[35][35][35][35]; //表示第一次走到第i行，第j列，第二次到达第k行，第l列能获得的最大值。
   int main() {
   	cin >> n;
   	while(cin >> x >> y >> w) { //输入 
   		if(x == 0 && y == 0 && w == 0) break; //退出 
   		a[x][y] = w;
   	}
   	for (int i = 1; i <= n; i++)
   		for (int j = 1; j <= n; j++)
   			for (int k = 1; k <= n; k++)
   				for (int l = 1; l <= n; l++) {
   					int t1 = max(f[i - 1][j][k - 1][l], f[i - 1][j][k][l - 1]); //记录 
   					int t2 = max(f[i][j - 1][k - 1][l], f[i][j - 1][k][l - 1]); //记录 
   					f[i][j][k][l] = max(t1, t2) + a[i][j] + a[k][l]; //求最大值 
   					if(i == k && j == l) f[i][j][k][l] -= a[i][j]; //如果位置相同，则减去其中一个 
   				}
   	cout << f[n][n][n][n] << endl; //答案 
   	return 0;
   }