题解

本题和 A147 是重题。

思路

用四维动态规划，按题意模拟即可。

状态转移

$$dp\left[x_{1} \bmod 2\right]\left[y_{1}\right]\left[x_{2}\right]\left[y_{2}\right]=\max \left\{\begin{array}{l} dp\left[\left(x_{1}-1\right) \bmod 2\right]\left[y_{1}\right]\left[x_{2}-1\right]\left[y_{2}\right], \\ dp\left[\left(x_{1}-1\right) \bmod 2\right]\left[y_{1}\right]\left[x_{2}\right]\left[y_{2}-1\right], \\ dp\left[x_{1} \bmod 2\right]\left[y_{1}-1\right]\left[x_{2}-1\right]\left[y_{2}\right], \\ dp\left[x_{1} \bmod 2\right]\left[y_{1}-1\right]\left[x_{2}\right]\left[y_{2}-1\right] \end{array}\right.$$

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int x,y,z;
int dp[2][10][10][10];// dp状态数组，用于优化空间，第一维用2进行滚动，表示两条路径
int a[10][10];
signed main(){
	cin>>n;
	// 按题意读取数字位置和值，直到遇到 0 0 0 结束
	while(true){
		cin>>x>>y>>z;
		if(x==0&&y==0&&z==0)break;
		a[x][y]=z;
	}
	// x1, y1 表示第1条路径当前位置坐标
    // x2, y2 表示第2条路径当前位置坐标
    // dp[x1%2][y1][x2][y2] 表示两条路径分别到达(x1,y1)和(x2,y2)时的最大和
	for(int x1=1;x1<=n;x1++){
		for(int y1=1;y1<=n;y1++){
			for(int x2=1;x2<=n;x2++){
				for(int y2=1;y2<=n;y2++){
					// 状态转移四种可能的上一状态：
                    // 路径1从(x1-1,y1)或(x1,y1-1)到达(x1,y1)
                    // 路径2从(x2-1,y2)或(x2,y2-1)到达(x2,y2)
					dp[x1%2][y1][x2][y2]=max(dp[(x1-1)%2][y1][x2-1][y2],max(dp[(x1-1)%2][y1][x2][y2-1],max(dp[x1%2][y1-1][x2-1][y2],dp[x1%2][y1-1][x2][y2-1])));
					if(x1==x2&&y1==y2)dp[x1%2][y1][x2][y2]+=a[x1][y1];// 如果两个路径当前在同一格子，只加一次
					else dp[x1%2][y1][x2][y2]+=a[x1][y1]+a[x2][y2];
				}
			}
		}
	}
	// 输出即可
	printf("%lld",dp[n%2][n][n][n]);
	return 0;
}