本文共 1716 字，大约阅读时间需要 5 分钟。
在这个问题中，我们需要计算两个从对角线的两个端点出发的移动者在n×n网格中相遇时的总分。第一个移动者从(1,1)出发，只能向右或向下移动；第二个移动者从(n,n)出发，只能向左或向上移动。每当他们走到同一个格子时，只累加一次该格子的分数。
我们可以使用动态规划来解决这个问题。定义状态dp[i][j][k]为第一个移动者走了i步，第二个移动者走了k步，此时第一个移动者位于第j行，第二个移动者位于第k行。由于每一步移动都会改变行或列的位置，且每个移动者的移动方向有限制，我们可以通过状态转移来计算最终的总分。
对于每一个状态i（即两人都走了i步），我们需要考虑第一个移动者和第二个移动者在i-1步时的可能位置，然后计算他们移动到当前位置的最大总分。
具体来说，第一个移动者在第i步可以从：
第二个移动者在第i步可以从：
对于每一种可能的转移，我们计算对应的分数，并将其与当前状态dp[i][j][k]进行比较，取最大值作为新的状态值。
#includeusing namespace std;typedef long long ll;const int maxn = 305;const int inf = 0x3f3f3f3f;int n, dp[maxn][maxn][maxn];ll a[maxn][maxn];int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { scanf("%d", &a[i][j]); } } memset(dp, -inf, sizeof(dp)); dp[1][1][1] = a[1][1]; for (int i = 1; i <= 2 * n - 1; ++i) { for (int j = 1; j <= n; ++j) { for (int k = 1; k <= n; ++k) { if (j > i || k > i) continue; if (j < 1 || k < 1) continue; int temp = a[j][i - j + 1] + (j != k ? a[k][i - k + 1] : 0); dp[i][j][k] = max( dp[i-1][j][k] + temp, dp[i-1][j-1][k] + temp, dp[i-1][j][k-1] + temp, dp[i-1][j-1][k-1] + temp ); } } } cout << dp[2 * n - 1][n][n] << endl;}
初始化：读取输入并初始化动态规划数组dp。dp[1][1][1]设置为起点的分数。
填充状态：通过三重循环遍历每一个可能的状态i（即两人走了i步）。对于每一个状态，计算第一个移动者和第二个移动者可能的转移位置，并更新当前状态的最大分数。
输出结果：最终输出dp[2n-1][n][n]，即两人都走了2n-1步后，第一个移动者到达(n,n)，第二个移动者也到达(n,n)的最大总分。
这种方法通过动态规划有效地计算了两移动者的路径分数之和，确保了所有可能的路径都被考虑进去了。
转载地址：http://leewz.baihongyu.com/